[백준/BOJ] 백준 1473번 : 미로 탈출

https://www.acmicpc.net/problem/1473

1473번: 미로 탈출

int discovered[1 << 7][1 << 7][7][7] 에 [회전된 행 체크(비트로 표현)][회전된 열 체크(비트로 표현)][here의 행위치][here의 열위치] = 깊이를 저장하여 bfs를 통해 문제를 해결한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <string>
using namespace std;

int n, m;
vector<string> board;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int discovered[1 << 7][1 << 7][7][7]; //[회전된 행 체크][회전된 열 체크][here의 행위치][here의 열위치] = 깊이

bool Can_Go(pair<int, int> here_point, pair<int, int> there_point, int dir, pair<int, int> board_status)
{
	vector<string> check_board = board;

	//board_status로 뒤집었을때 check_board 만들기
	for (int j = 0; j < m; j++)
	{
		//j열이 뒤집힌 열일때
		if ((board_status.second & (1 << j)) != 0)
		{
			for (int i = 0; i < n; i++)
			{
				if (check_board[i][j] == 'C')
					check_board[i][j] = 'D';

				else if (check_board[i][j] == 'D')
					check_board[i][j] = 'C';
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		//i행이 뒤집힌 행일때
		if ((board_status.first & (1 << i)) != 0)
		{
			for (int j = 0; j < m; j++)
			{
				if (check_board[i][j] == 'C')
					check_board[i][j] = 'D';

				else if (check_board[i][j] == 'D')
					check_board[i][j] = 'C';
			}
		}
	}

	char here = check_board[here_point.first][here_point.second];
	char there = check_board[there_point.first][there_point.second];

	if (here == 'A')
	{
		if (dir == 0)
		{
			if (there == 'A' || there == 'D')
				return true;
		}

		else if (dir == 1)
		{
			if (there == 'A' || there == 'C')
				return true;
		}

		else if (dir == 2)
		{
			if (there == 'A' || there == 'D')
				return true;
		}

		else if (dir == 3)
		{
			if (there == 'A' || there == 'C')
				return true;
		}
	}

	else if (here == 'C')
	{

		if (dir == 1)
		{
			if (there == 'A' || there == 'C')
				return true;
		}

		else if (dir == 3)
		{
			if (there == 'A' || there == 'C')
				return true;
		}
	}

	else if (here == 'D')
	{
		if (dir == 0)
		{
			if (there == 'A' || there == 'D')
				return true;
		}

		else if (dir == 2)
		{
			if (there == 'A' || there == 'D')
				return true;
		}
	}

	return false;
}

int Solve(pair<int, int> start, pair<int, int> dest)
{
	queue<tuple<int, int, int, int>> q;

	for (int i = 0; i < (1 << 7); i++)
		for (int j = 0; j < (1 << 7); j++)
			for (int k = 0; k < 7; k++)
				for (int l = 0; l < 7; l++)
				{
					discovered[i][j][k][l] = -1;
				}

	discovered[0][0][start.first][start.second] = 0;
	q.push(make_tuple(0, 0, start.first, start.second));

	while (!q.empty())
	{
		tuple<int, int, int, int> here = q.front();
		q.pop();
		pair<int, int> here_board = make_pair(get<0>(here), get<1>(here));
		pair<int, int> here_point = make_pair(get<2>(here), get<3>(here));

		if (here_point == dest)
			return discovered[get<0>(here)][get<1>(here)][get<2>(here)][get<3>(here)];

		//움직이는 경우
		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there_point = make_pair(here_point.first + dxdy[i][0], here_point.second + dxdy[i][1]);

			if (there_point.first >= 0 && there_point.first < n && there_point.second >= 0 && there_point.second < m)
			{
				if (Can_Go(here_point, there_point, i, here_board) && discovered[here_board.first][here_board.second][there_point.first][there_point.second] == -1)
				{
					discovered[here_board.first][here_board.second][there_point.first][there_point.second] = discovered[here_board.first][here_board.second][here_point.first][here_point.second] + 1;
					q.push(make_tuple(here_board.first, here_board.second, there_point.first, there_point.second));
				}
			}
		}

		//here의 행 열을 90도 뒤집는 경우
		pair<int, int> there_board = here_board;

		//here위치의 행 뒤집기
		there_board.first ^= (1 << here_point.first);

		//here위치의 열 뒤집기
		there_board.second ^= (1 << here_point.second);

		if (discovered[there_board.first][there_board.second][here_point.first][here_point.second] == -1)
		{
			discovered[there_board.first][there_board.second][here_point.first][here_point.second] = discovered[here_board.first][here_board.second][here_point.first][here_point.second] + 1;
			q.push(make_tuple(there_board.first, there_board.second, here_point.first, here_point.second));
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	cout << Solve(make_pair(0, 0), make_pair(n - 1, m - 1));

	return 0;
}