글 읽기 - 진짜 반례가 없습니다. ㅠㅠㅠㅠㅠㅠㅠ

heroswift15 5년 전 0

과연 진짜 반례가 없을까요????????? 이 BFS 에 오류가 있는걸꺼요??.

#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;
}

slsnsepdpd 5년 전 0

if(visit[nexty][nextx][0]==0 && nextchk==0)
{
if(nextchk==0){
visit[nexty][nextx][0]=1;
enque(nexty, nextx, nextrange+1,nextchk);

}
}

55번 줄 이 부분이 문제 아닐까요? 다음 칸이 빈칸이면 벽을 부순 적이 있던 지 없던 지 상관없이 다음 칸으로 갈 수 있어야 하는 것 같은데요.

그리고 또 문제점으로 보이는 것이 55번줄 부터 지도를 체크할 때

if(visit[nexty][nextx][0] == 0)..

이런식으로 하는데요, 이 부분을 visit[nexty][nextx][nextchk] 이런 식으로 해야 현재 상태의 맵(벽을 부수기 전 or 부순 후인 지)을 올바르게 서치할 수 있을 것 같은데요.

slsnsepdpd 5년 전 7

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

아래 어떤 분이 올려주신 반례입니다.

정답은 29입니다.

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

문제

문제

출처

ICPC

진짜 반례가 없습니다. ㅠㅠㅠㅠㅠㅠㅠ

heroswift15 5년 전 0

slsnsepdpd 5년 전 0

slsnsepdpd 5년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말