글 읽기 - 4179 불! 질문드립니다.

eollyea 3년 전 0

아무리 확인해도 맞는것 같은데 계속 틀렸다고 나오네요

질문글들에 반례들도 다 해봤는데 맞게 나오는데,

어디가 잘못된 걸까요?

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string board[1002];
int dist1[1002][1002]; //f
int dist2[1002][1002]; //j

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(void){
	int n,m,i,j;
	queue<pair<int,int> > Q1;
	queue<pair<int,int> > Q2;
	
	scanf("%d",&m);
	scanf("%d",&n);
	for(i = 0; i < n; i++)
    	cin >> board[i];     	
    	
    	
    for(i=0; i<n; i++){
    	for(j=0; j<m; j++){
    		if(board[i][j]=='F'){
    			Q1.push({i,j});
			}
			else if(board[i][j]=='J'){
				Q2.push({i,j});
			}
		}
	}
		
	while(!Q1.empty()){
		pair<int,int> cur = Q1.front(); Q1.pop();
		for(int dir=0; dir<4; dir++){
			int nx=cur.X + dx[dir];
			int ny=cur.Y + dy[dir];
			if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
			if(board[nx][ny]=='#' || dist1[nx][ny]>0) continue;
			dist1[nx][ny]=dist1[cur.X][cur.Y]+1;
			Q1.push({nx,ny});	
		}
	}
	
	while(!Q2.empty()){
		pair<int,int> cur = Q2.front(); Q2.pop();
		for(int dir=0; dir<4; dir++){
			int nx=cur.X + dx[dir];
			int ny=cur.Y + dy[dir];
			if(nx<0 || ny<0 || nx>=n || ny>=m){
				printf("%d",dist2[cur.X][cur.Y]+1);
				return 0;
			}
			if(dist2[nx][ny]>0 || board[nx][ny]=='#') continue;
			if(dist1[nx][ny]!=0 && dist2[cur.X][cur.Y]+1>=dist1[nx][ny]) continue;
			dist2[nx][ny]=dist2[cur.X][cur.Y]+1;
			Q2.push({nx,ny});
		}
	}
	printf("IMPOSSIBLE");
}

3587jjh 3년 전 1

지훈이가 처음부터 미로의 가장자리에 접한 공간에 있는 경우가 고려되어있지 않습니다

eollyea 3년 전 0

답변 감사드립니다. 다시 해보겠습니다.

eollyea 3년 전 0

지훈이가 처음부터 가장자리에 있는 경우를 고려하여 새로 짜보았는데 틀리게 나옵니다.

근데 어차피 59~61줄 보시면 범위밖으로 나가면 탈출한걸로 되어있는데

가장자리에 있는경우를 따로 고려하지 않아도 괜찮지 않나요?

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string board[1002];
int dist1[1002][1002]; //f
int dist2[1002][1002]; //j

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(void){
	int n,m,i,j;
	queue<pair<int,int> > Q1;
	queue<pair<int,int> > Q2;
	
	scanf("%d",&m);
	scanf("%d",&n);
	for(i = 0; i < n; i++)
    	cin >> board[i];     	
    	
    		
    for(i=0; i<n; i++){
    	for(j=0; j<m; j++){
    		if(board[i][j]=='F'){
    			Q1.push({i,j});
			}
			else if(board[i][j]=='J'){
				// 지훈이가 처음부터 가장자리에 있는 경우 		 
				if(i==0 || j==0 || i==n-1 || j==m-1){
					printf("1");
					return 0;
				}
				Q2.push({i,j});				
			}
		}
	}
		
	while(!Q1.empty()){
		pair<int,int> cur = Q1.front(); Q1.pop();
		for(int dir=0; dir<4; dir++){
			int nx=cur.X + dx[dir];
			int ny=cur.Y + dy[dir];
			if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
			if(board[nx][ny]=='#' || dist1[nx][ny]>0) continue;
			dist1[nx][ny]=dist1[cur.X][cur.Y]+1;
			Q1.push({nx,ny});	
		}
	}
	
	while(!Q2.empty()){
		pair<int,int> cur = Q2.front(); Q2.pop();
		for(int dir=0; dir<4; dir++){
			int nx=cur.X + dx[dir];
			int ny=cur.Y + dy[dir];
			if(nx<0 || ny<0 || nx>=n || ny>=m){
				printf("%d",dist2[cur.X][cur.Y]+1);
				return 0;
			}
			if(dist2[nx][ny]>0 || board[nx][ny]=='#') continue;
			if(dist1[nx][ny]!=0 && dist2[cur.X][cur.Y]+1>=dist1[nx][ny]) continue;
			dist2[nx][ny]=dist2[cur.X][cur.Y]+1;
			Q2.push({nx,ny});
		}
	}
	printf("IMPOSSIBLE");
}

djm03178 3년 전 1

행의 수, 열의 수 순으로 입력이 주어지는데 이 코드는 반대로 입력받고 있습니다.

eollyea 3년 전 0

아 그러네요 덕분에 해결됐습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4179 불! 질문드립니다.

eollyea 3년 전 0

3587jjh 3년 전 1

eollyea 3년 전 0

eollyea 3년 전 0

djm03178 3년 전 1

eollyea 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말