백준 16197번 두 동전 C++

출처 : https://www.acmicpc.net/problem/16197

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int n, m;
vector<vector<char>> board;
vector<vector<vector<vector<bool>>>> found;

struct Coins {
	pair<int, int> coin1;
	pair<int, int> coin2;
	int moveCnt;
};

int main()
{
	cin >> n >> m;
	board = vector<vector<char>>(n, vector<char>(m));
	found = vector<vector<vector<vector<bool>>>>(n, vector<vector<vector<bool>>>(m, vector<vector<bool>>(n, vector<bool>(m, false))));
	vector<pair<int, int>> initCoins;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'o') initCoins.push_back({ i,j });
		}
	}
	pair<int, int> coin1 = initCoins[0];
	pair<int, int> coin2 = initCoins[1];
	queue<Coins> q;
	q.push({ coin1,coin2,0 });
	found[coin1.first][coin1.second][coin2.first][coin2.second] = true;

	int ans = -1;

	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		bool finished = false;
		for (int i = 0; i < 4; i++) {
			int cnt = 0;
			int nextRow1 = curr.coin1.first + dRow[i];
			int nextCol1 = curr.coin1.second + dCol[i];

			int nextRow2 = curr.coin2.first + dRow[i];
			int nextCol2 = curr.coin2.second + dCol[i];
			if (nextRow1 < 0 || nextRow1 >= n || nextCol1 < 0 || nextCol1 >= m) {
				cnt++;
			}
			if (nextRow2 < 0 || nextRow2 >= n || nextCol2 < 0 || nextCol2 >= m) {
				cnt++;
			}
			if (cnt == 2) continue;
			if (cnt == 1) {
				ans = curr.moveCnt + 1;
				finished = true;
				break;
			}
			if (board[nextRow1][nextCol1] == '#') {
				nextRow1 = curr.coin1.first;
				nextCol1 = curr.coin1.second;
			}
			if (board[nextRow2][nextCol2] == '#') {
				nextRow2 = curr.coin2.first;
				nextCol2 = curr.coin2.second;
			}
			if (found[nextRow1][nextCol1][nextRow2][nextCol2]) continue;
			found[nextRow1][nextCol1][nextRow2][nextCol2] = true;
			q.push({ {nextRow1,nextCol1},{nextRow2,nextCol2},curr.moveCnt + 1 });
		}
		if (finished) break;
	}
	if (ans > 10) ans = -1;
	cout << ans;
}