글 읽기 - 어디가 틀렸는지 잘 모르겠습니다.

titane308 5년 전 0

테스트 케이스는 모두 통과했으나 틀렸다고 떠서 어떤 반례로 인해 틀렸는지 잘 모르겠습니다.

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
using namespace std;
#define DIR 3
int dist[10][10][10][10];
string a[10];
int dir[4] = { 1,-1,0,0 };
int n, m;

pair<bool, bool> simulate(int &x, int &y, int k)
{
	bool moved = false;
	while (a[y][x]=='R' || a[y][x]=='B')
	{
		int nx = x + dir[k];
		int ny = y + dir[DIR - k];
		if (nx < 0 || nx >= m || ny < 0 || ny >= n)
			return make_pair(moved, false);
		if (a[ny][nx] == '#' || a[ny][nx] == 'R' || a[ny][nx] == 'B')
			return make_pair(moved, false);
		else if (a[ny][nx] == '.')
		{
			swap(a[ny][nx], a[y][x]);
			x = nx; y = ny;
			moved = true;
		}
		else if (a[ny][nx] == 'O')
		{
			a[y][x] = '.';
			moved = true;
			return make_pair(moved, true);
		}
	}
	return make_pair(moved, false);
}

pair<bool, bool> go(int &rx, int &ry, int &bx, int &by, int k)
{
	a[ry][rx] = 'R';
	a[by][bx] = 'B';
	bool hole1 = false, hole2 = false;
	while (1)
	{
		auto p1 = simulate(rx, ry, k);
		auto p2 = simulate(bx, by, k);
		if (!p1.first && !p2.first)
		{
			return make_pair(hole1, hole2);
		}
		if (p2.second)
		{
			hole2 = true;
		}
		if (p1.second)
		{
			hole1 = true;
		}
	}
	return make_pair(hole1, hole2);
}

int main()
{
	cin >> n >> m;
	int rx, ry, bx, by;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 'R')
			{
				rx = j; ry = i;
				a[i][j] = '.';
			}
			else if (a[i][j] == 'B')
			{
				bx = j; by = i;
				a[i][j] = '.';
			}
		}
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < n; k++) for (int l = 0; l < m; l++) dist[i][j][k][l] = -1;
	queue<tuple<int, int, int, int>> q;
	dist[ry][rx][by][bx] = 0;
	q.emplace(rx, ry, bx, by);
	while (!q.empty())
	{
		tie(rx, ry, bx, by) = q.front();
		q.pop();
		for (int k = 0; k <= DIR; k++)
		{
			int nrx = rx, nry = ry;
			int nbx = bx, nby = by;
			bool hole1 = false, hole2 = false;
			tie(hole1, hole2) = go(nrx, nry, nbx, nby, k);
			if (hole2) continue;
			if (hole1)
			{
				cout << dist[ry][rx][by][bx] + 1 << '\n';
				return 0;
			}
			if (dist[nry][nrx][nby][nbx] != -1) continue;
			q.emplace(nrx, nry, nbx, nby);
			dist[nry][nrx][nby][nbx] = dist[ry][rx][by][bx] + 1;
		}
	}
	cout << -1 << '\n';
}

djm03178 5년 전 0

https://www.acmicpc.net/board/... 이 문제와 사실상 똑같은 문제니 (10번 이하 조건 빼고) 여기서 반례를 먼저 찾아보세요.

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

문제

문제

출처

ICPC

어디가 틀렸는지 잘 모르겠습니다.

titane308 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말