글 읽기 - 반례를 찾아주실 수 있을까요?

stronghsg 4년 전 0

반례를 찾아주실수 있을까요?

혹은 논리적으로 잘못된 부분 지적 부탁드립니다..

35%정도에서 틀림이 나오네요 ㅠㅠ

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int check[1000][1000][2]; // [0]: 방문여부, [1]: 벽부숨 여부
int nodes[1000][1000];

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

void bfs(int x, int y, int W, int H)
{
	queue <tuple<int, int, int>> cur; // x, y, 벽부수지 않은경우
	queue <tuple<int, int, int>> next; // x, y, 벽부숨
	int visit = 1;
	check[y][x][0] = visit; // 방문
	int wall = 0;
	check[y][x][1] = wall; // 벽 안부숨
	cur.push(make_tuple(0, 0, wall));
	while (!cur.empty())
	{
		int cur_x, cur_y, cur_w;
		tie(cur_x, cur_y, cur_w) = cur.front();
		cur.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_x = cur_x + dx[i];
			int next_y = cur_y + dy[i];
			if (0 <= next_x && next_x < W && 0 <= next_y && next_y < H)
			{ // 범위 안이라면
				if (check[next_y][next_x][0] == 0)
				{ // 다음 방문한적 x
					if (cur_w == 0)
					{// 현재까지 벽 부순적 없다면
						if (nodes[next_y][next_x] == 1)
						{// 다음이 벽이라면
							wall = 1; //벽 부수고 check
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							next.push(make_tuple(next_x, next_y, wall));
						}
						if (nodes[next_y][next_x] == 0)
						{//다음이 벽이 아니라면
							wall = 0; //벽 부수지 않고 check
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							cur.push(make_tuple(next_x, next_y, wall));
						}
					}
					else
					{// 현재까지 벽 부순적 있다면
						if (nodes[next_y][next_x] == 0)
						{// 다음에 벽이 없다면 부수지 않고 check
							wall = 1; // 이미 부쉈으므로
							visit = check[cur_y][cur_x][0] + 1;
							check[next_y][next_x][0] = visit;
							check[next_y][next_x][1] = wall;
							next.push(make_tuple(next_x, next_y, wall));
						}
					}
				}
				if (next_x == W - 1 && next_y == H - 1)
				{// 다음이 마지막 노드라면
					if (check[next_y][next_x][0] == 1)
					{//방문을 했던 경우라도
					 // 새로운 값이 작으면 작은거로 check
						int now = check[cur_y][cur_x][0] + 1; //현재 노드에서 계산된 값이
						int prev = check[next_y][next_x][0]; // 저장되어있던 값보다
						if (now < prev) check[next_y][next_x][0] = now; // 작다면 작은값으로 초기화
					}
				}
			}
		}
		if (cur.empty())
		{
			cur = next;
			next = queue<tuple<int, int, int>>();
		}
	}
}

int main()
{
	int H, W; // N=X, M=Y
	scanf("%d %d", &H, &W);
	for (int j = 0; j < H; j++)
	{
		for (int i = 0; i < W; i++)
		{
			scanf("%1d", &nodes[j][i]);
		}
	}

	bfs(0, 0, W, H);

	int result = check[H - 1][W - 1][0];
	if (result)	printf("%d\n", result);
	else printf("-1\n");

	//system("pause");
	return 0;
}

nahwasa 4년 전 6

반례입니다.

정답은 우측으로 가다가 도착점 바로 위의 벽을 깨는것이구요.

님 소스로는 출발점 아래의 벽을 깨고 도착점 2칸 위에 도착한것때문에 해당 위치에 방문체크가 되어

정답길로 안간듯합니다.

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

문제

문제

출처

ICPC

반례를 찾아주실 수 있을까요?

stronghsg 4년 전 0

nahwasa 4년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말