글 읽기 - HELP ME!!!

pos10022 7년 전 0

어디가 틀렸는지 모르겠어요.

#include <stdio.h>
#define N 1005

int n,m,a;
int chk[N][N],q[N*N][2],f,r,v[N][N];
char map[N][N];

void bfs()
{
	int y,x;

	q[r][0]=1;
	q[r++][1]=1;

  	v[1][1]=1;

	y=1;
	x=1;      

	chk[1][1]=1;

	while(f<r) {
		y=q[f][0]; x=q[f++][1];
		if(y<n && v[y+1][x]==0 && (map[y+1][x]=='0' || (map[y+1][x]=='1' && map[y+2][x]=='0' && a==0))) {
			if(map[y+1][x]=='1' && map[y+2][x]=='0' && a==0) 
			{ map[y+1][x]='0'; a=1; }
			if(chk[y+1][x]==0) chk[y+1][x]=chk[y][x]+1;
			else {
				if(chk[y+1][x]>chk[y][x]+1) chk[y+1][x]=chk[y][x]+1;
			}
			q[r][0]=y+1; q[r++][1]=x;
			v[y][x]=1;
		}
		if(y>1 && v[y-1][x]==0 &&  (map[y-1][x]=='0' || (map[y-1][x]=='1' && map[y-2][x]=='0' && a==0))) {
			if(map[y-1][x]=='1' && map[y-2][x]=='0' && a==0)  
			{ map[y-1][x]='0'; a=1; }
			chk[y-1][x]=chk[y][x]+1;
			if(chk[y-1][x]==0) chk[y-1][x]=chk[y][x]+1;
			else {
				if(chk[y-1][x]>chk[y][x]+1) chk[y-1][x]=chk[y][x]+1;
			}
			q[r][0]=y-1; q[r++][1]=x;
			v[y][x]=1;
		}
		if(x<m && v[y][x+1]==0 &&  (map[y][x+1]=='0' || (map[y][x+1]=='1' && map[y][x+2]=='0' && a==0))) {
			if(map[y][x+1]=='1' && map[y][x+2]=='0' && a==0) 
			{ map[y][x+1]='0'; a=1; }
			if(chk[y][x+1]==0) chk[y][x+1]=chk[y][x]+1;
			else {
				if(chk[y][x+1]>chk[y][x]+1) chk[y][x+1]=chk[y][x]+1;
			}
			q[r][0]=y; q[r++][1]=x+1;
			v[y][x]=1;
		}
		if(x>1 && v[y][x-1]==0 &&  (map[y][x-1]=='0' || (map[y][x-1]=='1' && map[y][x-2]=='0' && a==0))) {
			if(map[y][x-1]=='1' && map[y][x-2]=='0' && a==0) 
			{ map[y][x-1]='0'; a=1; }
			if(chk[y][x-1]==0) chk[y][x-1]=chk[y][x]+1;
			else {
				if(chk[y][x-1]>chk[y][x]+1) chk[y][x-1]=chk[y][x]+1;
			}
			q[r][0]=y; q[r++][1]=x-1;
			v[y][x]=1;
		}
	}
}

int main()
{
	int i,j;

	scanf("%d %d",&n,&m);

	for(i=1;i<=n;i++) {
		scanf("%s",map[i]+1);
	}

	bfs();

	if(chk[n][m]==0) printf("-1\n");
	else printf("%d\n",chk[n][m]);
}

zlzmsrhak 7년 전 1

반례입니다.

인접한 칸을 부순 뒤 방향을 바꿔 이동하는 경우가 처리가 되지 않았습니다. 예를 들어,

오른쪽 칸을 부순 뒤 아래나 위쪽으로 이동할 수 있는 경우가 처리가 되지 않았습니다.

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

문제

문제

출처

ICPC

HELP ME!!!

pos10022 7년 전 0

zlzmsrhak 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말