13460번 구슬 탈출2

#include <iostream>
#include <vector>
#include <string>
using namespace std;


int n, m;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
pair<bool, bool> sim(vector<string>& a, int k, int& x, int& y) {
	if (a[x][y] == '.') return make_pair(false, false);
	bool moved = false;
	while (1) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
			return make_pair(moved, false);
		}
		if (a[nx][ny] == '#') {
			return make_pair(moved, false);
		}
		else if (a[nx][ny] == 'R' || a[nx][ny] == 'B') {
			return make_pair(moved, false);
		}
		else if (a[nx][ny] == '.') {
			swap(a[nx][ny], a[x][y]);
			x = nx;
			y = ny;
			moved = true;
		}
		else if (a[nx][ny] == 'O') {
			a[x][y] = '.';
			moved = true;
			return make_pair(moved, true);
		}
	}
	return make_pair(false, false);
}
int check(vector<string>a, vector<int>& dir) {
	int hx, hy, rx, ry, bx, by;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'O') {
				hx = i; hy = j;
			}
			else if (a[i][j] == 'R') {
				rx = i; ry = j;
			}
			else if (a[i][j] == 'B') {
				bx = i, by = j;
			}
		}
	}
	int cnt = 0;
	for (int k : dir) {
		cnt++;
		bool hole1 = false, hole2 = false;
		while (1) {
			pair<bool, bool> p1 = sim(a, k, rx, ry);
			pair<bool, bool> p2 = sim(a, k, bx, by);
			if (p1.first == false && p2.first == false) break;
			if (p1.second) hole1 = true;
			if (p2.second) hole2 = true;
		}
		if (hole2) return -1;
		if (hole1) return cnt;
	}
	return -1;
}
int ans=-1;
vector<int> dir;
void DFS(vector<string>& a,int L,int last) {
	if (L == 10) {
		int cur = check(a, dir);
		if (cur == -1)return;
		if (ans == -1 || ans > cur) ans = cur;
		return;
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (last == i) continue;
			dir.push_back(i);
			DFS(a,L + 1,i);
			dir.pop_back();
		}
	}
}

int main() {
	//freopen("in1.txt", "rt", stdin);
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	DFS(a,0,-1);
	cout << ans << '\n';
	return 0;
}