글 읽기 - 제가 무엇을 놓치고 있는지 잘 모르겠습니다. 부탁드리겠습니다.

park780172 4년 전 0

위에 있는 테스트 케이스들은 제가 생각해본 반례들입니다.

93%에서 계속 틀렸습니다가 떠서, 제가 생각하기에 특수한 케이스인 것 같습니다.

제가 무엇을 놓치고 있는지 잘 모르겠습니다.

반례와 함께 지적도 같이 해주시길 부탁드리겠습니다!

#include <bits/stdc++.h>

using namespace std;

int m[1001][1001], r, w, L, R, sy, sx;

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

typedef struct info
{
	int y, x, left, right;
}info;

bool visit[1010][1010];

queue<info> q;

int bfs()
{
	int ret = 1; // 출발 지점 포함하므로, 1이다.

	q.push({ sy, sx, L, R });

	visit[sy][sx] = true;

	while (!q.empty())
	{
		int qSize = q.size();

		while (qSize--)
		{
			int y = q.front().y, x = q.front().x;
			int Left = q.front().left, Right = q.front().right;

			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int ny = y + dy[i], nx = x + dx[i];

				// 범위에 맞지 않거나 방문을 한 적 있는 곳이거나 장애물이면 continue
				if (ny < 0 || ny >= r || nx < 0 || nx >= w || visit[ny][nx] || m[ny][nx]) continue;

				if (i == 2 && Left > 0) // 왼 쪽(dy, dx 배열의 인덱스 번호가 2)
				{
					// 왼 쪽으로 갔으므로, Left는 1 감소된다.
					q.push({ ny, nx, Left - 1, Right });
					visit[ny][nx] = true;
					++ret;
				}

				if (i == 0 && Right > 0) // 오른 쪽(dy, dx 배열의 인덱스 번호가 0)
				{
					// 오른 쪽으로 갔으므로, Right는 1 감소된다.
					q.push({ ny, nx, Left, Right - 1 });
					visit[ny][nx] = true;
					++ret;
				}		

				// '좌' 또는 '우'라면, continue 
				if (i == 0 || i == 2) continue;

				// '상' 또는 '하'라면
				q.push({ ny, nx, Left, Right }); // Left, Right 모두 감소되지 않는다.
				visit[ny][nx] = true;
				++ret;
			}
		}
	}

	return ret;
}

int main(void)
{
	scanf("%d %d %d %d", &r, &w, &L, &R);

	for (int i = 0; i < r; i++)
		for (int j = 0; j < w; j++)
		{
			scanf("%1d", &m[i][j]);
			if (m[i][j] == 2) sy = i, sx = j;
		}

	printf("%d\n", bfs());

	return 0;
}

nahwasa 4년 전 0

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

위아래로 한칸씩 이동하셨기 때문이네요!

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

문제

문제

출처

ICPC

제가 무엇을 놓치고 있는지 잘 모르겠습니다. 부탁드리겠습니다.

park780172 4년 전 0

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말