13460번 구슬 탈출2 비트 마스크

 

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
/*0    1  2      3
  아래 위 오른쪽 왼쪽*/

const int LIMIT = 10;

vector<int> gen(int k) { // 정수 k를 4진법으로 바꿈
	vector<int> a(LIMIT);
	for (int i = 0; i < LIMIT; i++) {
		a[i] = (k & 3); // k%4  if k=6 , 0110 & 0011 -> 0010 -> 2 
		k >>= 2; // k/4 if k=6, 0110 >>2 -> 0011 -> 0001 -> 1
	}
	return a;
}

pair<bool, bool> simulate(vector<string> &a, int k, int &x, int &y) {
	if (a[x][y] == '.') return make_pair(false, false);
	int n = a.size();
	int m = a[0].size();
	bool moved = false; // 움직였는지 안움직였는지
	while (true) {
		// 구슬 이동 계산
		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 n = a.size(); // 행 갯수
	int m = a[0].size(); // 열갯수

	//각 위치 구하기
	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 += 1; //몇번 움직였나
		bool hole1 = false, hole2 = false; // hole1 빨간구슬이 빠졌는지 hole2 파란 구슬이 빠졌는지
		while (true) {
			auto p1 = simulate(a, k, rx, ry); // 리턴값 (구슬이 움직였는지, 구멍에 빠졌는지)
			auto p2 = simulate(a, k, bx, by);
			if (p1.first == false && p2.first == false) { // 두 구슬이 움직이지 않았다면 while 종료
				break;
			}
			if (p1.second) hole1 = true;
			if (p2.second) hole2 = true;
		}
		if (hole2) return -1; // 파란구슬 빠지면 실패 리턴해서 함수 종료
		if (hole1) return cnt; // 빨란구슬 빠지면 cnt 리턴해서 함수 종료
	}
	return -1; // for문을 다 돌았는데 결과가 없으면 실패로 함수 종료
}

bool valid(vector<int> &dir) { //방향이 올바른가
	int l = dir.size();
	for (int i = 0; i + 1 < l; i++) {
		if (dir[i] == 0 && dir[i + 1] == 1) return false; // 아래 위
		if (dir[i] == 1 && dir[i + 1] == 0) return false; // 위 아래
		if (dir[i] == 2 && dir[i + 1] == 3) return false; //오른쪽 왼쪽
		if (dir[i] == 3 && dir[i + 1] == 2) return false; //왼쪽 오른쪽
		if (dir[i] == dir[i + 1]) return false; // 같은 방향 연속
	}
	return true;
}
int main() { //4진법 수로 풀이
	int n, m;
	cin >> n >> m;
	vector<string> a(n);
	
	for (int i = 0; i < n; i++) { // 입력받음
		cin >> a[i];
	}

	int ans = -1; // 불가능한 경우 -1 

	for (int k = 0; k < (1 << (LIMIT * 2)); k++) { // 2^20 경우의 수 만듬 == 4^10
		vector<int> dir = gen(k); // 실제 0123 으로 바꿔주는 함수
		if (!valid(dir)) continue; //방향이 올바른 방향인가  // 같은 방향으로 두번 되는지, 반대방향으로 연속해서 되는지 검사
		int cur = check(a, dir); // 게임판의 상태와 방향을 이용해 몇번만에 성공하는지 리턴
		if (cur == -1) continue; // 그 값이 -1 (불가능) 이면 컨틴뉴
		if (ans == -1 || ans > cur) ans = cur; // 처음이거나 ans보다 cur이 작을 때 ans=cur
	}

	cout << ans << '\n';
	
	return 0;
}

너무 길다.. 다시 풀어보기 ;;;