글 읽기 - 백준에서 처음으로 질문글 올려봅니다 실패케이스를 못찾고있습니다

csh6103 6년 전 0

다른 질문 하신분들처럼 57퍼에서 실패했습니다가 나오는데

왜 실패했는지 ... 실패 케이스를 못찾겠습니다 ㅠㅠㅠ

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
using namespace std;

int map[1005][1005];
int visit0[1005][1005];
int visit1[1005][1005];

int temp_map[1005][1005];
int isBreak;

void my_copy()
{
	for (int i = 0; i < 1005; i++)
	{
		for (int j = 0; j < 1005; j++)
		{
			map[i][j] = temp_map[i][j];
		}
	}
}

int N, M;

class my
{
public:
	int x;
	int y;
};

queue<my> q;

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

bool check(int x, int y)
{
	if (x >= 0 && y >= 0 && x < M && y < N)
		return true;
	else
		return false;
}

void bfs()
{
	while (!q.empty())
	{
		my temp = q.front();
		q.pop();
		int x, y;

		for (int i = 0; i < 4; i++)
		{
			x = temp.x + dx[i];
			y = temp.y + dy[i];

			if (true == check(x, y))
			{
				if (visit1[y][x] == 1 && visit0[y][x] != 0 && visit1[temp.y][temp.x] ==0 && map[y][x]==0)
				{
					visit0[y][x] = visit0[temp.y][temp.x] + 1;
					visit1[y][x] = visit1[temp.y][temp.x];
					my temp2;
					temp2.x = x;
					temp2.y = y;
					q.push(temp2);
				}
				else if (visit1[y][x] == 1 && visit0[y][x] != 0 && visit1[temp.y][temp.x] == 0 && map[y][x] == 1)
				{
					visit0[y][x] = visit0[temp.y][temp.x] + 1;
					visit1[y][x] = 1;
					my temp2;
					temp2.x = x;
					temp2.y = y;
					q.push(temp2);
				}
				else if (visit0[y][x] == 0 && map[y][x] == 0)
				{
					visit0[y][x] = visit0[temp.y][temp.x] + 1;
					visit1[y][x] = visit1[temp.y][temp.x];
					my temp2;
					temp2.x = x;
					temp2.y = y;
					q.push(temp2);
				}
				else if (map[y][x] == 1 && visit1[temp.y][temp.x] == 0)
				{
					visit1[y][x] = 1;
					visit0[y][x] = visit0[temp.y][temp.x] + 1;
					my temp2;
					temp2.x = x;
					temp2.y = y;
					q.push(temp2);
				}
				else if (visit1[temp.y][temp.x] == 0 && visit1[y][x] == 1 && visit0[y][x] == visit0[temp.y][temp.x] + 1)
				{
					visit1[y][x] = 0;
					visit0[y][x] = visit0[temp.y][temp.x] + 1;
					my temp2;
					temp2.x = x;
					temp2.y = y;
					q.push(temp2);
				}
				
			}
		}
	}
}

int main()
{
	//freopen("Text.txt", "r", stdin);

	scanf("%d %d", &N, &M);

	char temp[1005];
	for (int i = 0; i < N; i++)
	{
		scanf("%s", temp);
		for (int j = 0; j < M; j++)
		{
			map[i][j] = temp[j] - '0';
			temp_map[i][j] = temp[j] - '0';
		}
	}
	
	my start;
	start.x = 0;
	start.y = 0;

	q.push(start);
	visit0[0][0] = 1;
	if (map[0][0] == 1)
		visit1[0][0] = 1;
	

	bfs();

	/*cout << "--" << endl;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << visit[i][j][0];
		}
		cout << endl;
	}*/

	if (visit0[N - 1][M - 1] ==0)
		cout << -1 << endl;
	else
		cout << visit0[N-1][M-1] << endl;

}

djm03178 6년 전 1

62번째 줄부터 분기가 너무 많아 보이는데, 왜 저만큼이 필요하고 각각이 어떤 경우를 의미하는지 설명을 해주시면 좋겠네요.

Green55 6년 전 1

5 6
000000
011110
010000
010111
100000

csh6103 6년 전 0

반례찾아주신분 정말 감사합니다

코드가 이상한 이유는 졸린상태로 이것저것 마구 바꾸다보니 이상해진것같습니다...

csh6103 6년 전 0

원인을 찾아보니 bfs에서 큐가 비어질때까지 계속 돌리다가 하던것을

그냥 맵 끝에 도달하면 bfs멈추게 하면 되는거였습니다..

if (x == M-1 && y == N-1)
   {
    visit0[N - 1][M - 1] = visit0[temp.y][temp.x]+1;
    return;
   }

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

문제

문제

출처

ICPC

백준에서 처음으로 질문글 올려봅니다 실패케이스를 못찾고있습니다

csh6103 6년 전 0

djm03178 6년 전 1

Green55 6년 전 1

csh6103 6년 전 0

csh6103 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말