글 읽기 - 'C' 모든 가능성 체크 했습니다. 그러나.. ㅠㅠ

heroswift15 5년 전 0

BFS 를 이용하여 여태까지 벽을 부순적이 있는지 에 대한 기억은 pop.chk 를 통해서 실현 해주었습니다.

이후 이동한거리 계산은 range 를 통하여 계산해주었습니다.

이후 다른 풀이에서 이용한 3차원 배열로 부술지 말지에대해 체크 해주었고요.

그리고 모든 페이지에 있는 반례를 넣어주어 빌드 했을때 모두 okay 였습니다.

근데 제출시 보니 틀렸습니다..

제가 빠트린게 있나요??? 로직상으로는 틀리지 않았다고 보는데. 도움을 요청하고싶습니다...

만약 반례가 있다면... 제가 쓴 글은 엄청 부끄러워 지겠죠 .... 도움 부탁드리겠습니다...

#include<stdio.h>
int N,M;
int map[1001][1001];
int visit[1001][1001][2]; // 벽을 부수고 이동 하는건지 아닌지 chk
//                   [1] 이면 벽을 부순애가 지나갈때.
//                   [0] 이면 벽을  안부순에가 지나갈때.
int vety[]={0,0,1,-1};
int vetx[]={1,-1,0,0};
int front,rear;

typedef struct q{
	int y,x,range,chk;
}q;
q queue[1001*1001];

void enque(int y,int x,int range,int chk)
{
 q temp;
 temp.y=y;
 temp.x=x;
 temp.range=range; // 현재 까지의 이동거리  전달
 temp.chk=chk; // 부순적이 있는지에 대한 기억 체크.
	queue[rear++]=temp;
}

q deque()
{
	return queue[front++];
}



int BFS()
{
	int i,nexty,nextx,nextrange,nextchk;

		while(rear != front)
		{
			q pop=deque();

				for(i=0;i<4;i++)
				{
					nexty = pop.y + vety[i];
					nextx = pop.x + vetx[i]; 
					nextrange = pop.range;
					nextchk = pop.chk;

					if(nexty==N && nextx==M)
						return nextrange+1;

					if(nexty>=1 && nexty<=N && nextx >=1 && nextx<=M)
					{
						if(map[nexty][nextx]==0)
						{
									if(visit[nexty][nextx][0]==0 && nextchk==0)
									{
										if(nextchk==0){
											visit[nexty][nextx][0]=1;
											enque(nexty, nextx, nextrange+1,nextchk);
										//	printf(" range :[%d]  위치[%d][%d]\n",nextrange+1,nexty,nextx);
										}
									}
						
								if(visit[nexty][nextx][1]==0 && nextchk==1)
								{
											visit[nexty][nextx][1]=1;
											enque(nexty, nextx, nextrange+1,nextchk);
										//	printf(" range :[%d]  위치[%d][%d]\n",nextrange+1,nexty,nextx);
										

								}
						}


						if(map[nexty][nextx]==1)
						{
							if(visit[nexty][nextx][1]==0 && nextchk==0)
							{
								visit[nexty][nextx][1]=1;
								nextchk=1;
								//printf(" 벽 부수기  range :[%d]  위치[%d][%d]\n",nextrange+1,nexty,nextx);
								enque(nexty, nextx, nextrange+1,nextchk);
							}
						}


					}
				}
		}
		return -1;
}



int main()
{
	int i,j;
	scanf("%d%d",&N,&M);

	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			scanf("%1d",&map[i][j]);

	enque(1,1,1,0);
	visit[1][1][0]=1;
	int ans=BFS();
	printf("%d",ans);


	return 0;
}

heroswift15 5년 전 0

와 진자 반례 못찾겠다...이게 왜 통과가 아니지

eldpswp99 5년 전 0

1 1
0

출력 : -1

답 : 1

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

문제

문제

출처

ICPC

'C' 모든 가능성 체크 했습니다. 그러나.. ㅠㅠ

heroswift15 5년 전 0

heroswift15 5년 전 0

eldpswp99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말