글 읽기 - 테스트뿐만 아니라 제가 만든 케이스도 다 맞는데 무엇이 문제일까요?

kiwonlee95 4년 전 0

고수님들

2206 번에서 제가 만든 테스트 케이스와 문제의 케이스는 다 맞는데 어떤 부분에서 반례가 생기는 것일까요??

답변 부탁드리겟습니다.

감사합니다.

#include <iostream>
#include <algorithm>
#include <queue>
#pragma warning(disable : 4996)
using namespace std;

const int MAX = 1001;

int N, M, ans = 987654321;

int map[MAX][MAX];
bool visited[MAX][MAX];

struct POS
{
	int x, y;
	bool flag = false;
	int dist;
};

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

void BFS()
{
	queue<POS> q;
	POS cur;
	cur.x = 1, cur.y = 1, cur.dist = 1;

	q.push(cur);

	visited[cur.x][cur.y] = true;

	while (!q.empty())
	{
		POS cur = q.front();
		q.pop();

		int cur_x = cur.x, cur_y = cur.y;

		if (cur.dist > ans)
			continue;

		if (cur_x == N && cur_y == M)
		{
			ans = cur.dist;

			return;
		}

		for (int dir = 0; dir < 4; dir++)
		{
			int next_x = cur_x + dx[dir], next_y = cur_y + dy[dir];

			if (next_x <= 0 || next_x > N || next_y <= 0 || next_y > M)
				continue;

			if (visited[next_x][next_y] == false && map[next_x][next_y] == 1)
			{
				if (cur.flag == false)
				{
					POS next;
					next.flag = true;
					next.x = next_x, next.y = next_y, next.dist = cur.dist + 1;

					q.push(next);
					visited[next_x][next_y] = true;
				}
				else
					continue;
			}
			
			if (visited[next_x][next_y] == false && map[next_x][next_y] == 0)
			{
				POS next;
				next.flag = cur.flag;
				next.x = next_x, next.y = next_y, next.dist = cur.dist + 1;

				q.push(next);
				visited[next_x][next_y] = true;
			}
		}
	}
}
int main()
{
	scanf("%d %d", &N, &M);

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

	BFS();

	if (ans == 987654321)
		cout << "-1" << endl;
	else
		cout << ans << endl;

    return 0;
}

djm03178 4년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

테스트뿐만 아니라 제가 만든 케이스도 다 맞는데 무엇이 문제일까요?

kiwonlee95 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말