구슬을 굴리는 것은 중력으로 한 쪽 면으로 구슬들이 몰리는 현상이다. 그래서 왼쪽 벽으로 모는 함수와 직사각형 보드를 각각 90, 180, 270도 돌리는 함수를 구현했다.
위 함수를 구현하여 DFS 및 모든 상황에 대해서 네 방향으로 기우는 모든 방향들을 탐색하려고 했다. 이 때 테스트 케이스들만을 돌려도 시간이 오래 걸렸다. 이 방법은 틀렸다, 왜냐하면 열 번 이하로 갈 수 있는 방향이 있음에도 DFS로 구현하면 최악의 경우 약 4^10의 탐색을 해야하기 때문이다. 또한 이미 같은 상황의 직사각형 보드를 목격하였으면 해당 보드에 대한 탐색은 무의미하다.
vector<vector> moveLeft(vector<vector>& v)
직사각형의 보드의 구슬을 왼쪽으로 모는 함수
1-1. '#', '.', '0'는 그대로 유지.
1-2. 구슬 발견을 할 시 빈 칸을 제외하고 막히는 곳을 찾아서 삽입.
1-3. 탐색 중 구멍을 발견할 시 성공 및 실패 판별.
vector<vector> rotateXXX(vector<vector>& t)
void solver(int cnt)
BFS를 이용하여 푸는 과정
[input] int cnt: 몇 회 기울였는지
3-1: BFS를 위한 큐에서 경우의 수를 얻는다.
3-2: 이전에 경험했던 보드의 상태인지 확인
3-3: 처음보는 보드이면 위의 1번 2번 함수를 이용하여 조건에 맞는지 탐색.
3-4: 다음 solver함수에서 큐의 pop을 할 횟수 갱신
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int T;
int N, M;
int i, j;
vector<vector<char>> t;
int answer = 0;
queue<vector<vector<char>>> q;
int qs;
vector<vector<int>> point;
vector<vector<char>> moveLeft(vector<vector<char>>& v) {
vector<vector<char>> ret;
int goal = 0;
int i, j, k;
for(i = 0; i < v.size(); i++) {
vector<char> tv;
tv.clear();
for(j = 0; j < v[i].size(); j++) {
//1-1
if(v[i][j] == '#' || v[i][j] == '.' || v[i][j] == 'O') {
tv.push_back(v[i][j]);
}
// red or blue
else {
for(k = tv.size() - 1; k >= 0; k--) {
//1-2
if(tv[k] == '#' || tv[k] == 'B' || tv[k] == 'R' || tv[k] == 'O') {
//1-3
if(tv[k] == 'O') {
if(v[i][j] == 'R') {
if(goal == 0)
goal = 1;
}
else {
goal = -1;
}
}
break;
}
}
if(goal == 0)
tv.insert(tv.begin() + k + 1, v[i][j]);
}
}
ret.push_back(tv);
}
if(goal != 0) {
ret.clear();
ret.resize(1);
if(goal == -1) {
ret[0].push_back('X');
}
else {
ret[0].push_back('O');
}
}
return ret;
}
vector<vector<char>> rotateOne(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t[0].size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ret[i].push_back(t[j][t[0].size() - i - 1]);
}
}
return ret;
}
vector<vector<char>> rotateTwo(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t.size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t[0].size(); j++) {
ret[i].push_back(t[t.size() - i - 1][t[0].size() - j - 1]);
}
}
return ret;
}
vector<vector<char>> rotateThree(vector<vector<char>>& t) {
vector<vector<char>> ret;
ret.resize(t[0].size());
for(int i = 0; i < ret.size(); i++) {
for(int j = 0; j < t.size(); j++) {
ret[i].push_back(t[t.size() - j - 1][i]);
}
}
return ret;
}
void solver(int cnt) {
if(cnt > 10)
return;
int into = 0;
for(int x = 0; x < qs; x++) {
//3-1
vector<vector<char>> vt = q.front();
q.pop();
int stop = 0;
vector<int> pv(4, 0);
//3-2
for(int i = 0; i < vt.size();i++) {
for(int j = 0; j < vt[0].size();j++) {
if(vt[i][j] == 'R') {
pv[0] = i;
pv[1] = j;
}
else if(vt[i][j] == 'B') {
pv[2] = i;
pv[3] = j;
}
}//cout << endl;
}
for(int i = 0; i < point.size(); i++) {
if(point[i][0] == pv[0] && point[i][1] == pv[1] && point[i][2] == pv[2] && point[i][3] == pv[3]) {
stop = 1;
}
}
//3-3
if(stop == 0)
{
point.push_back(pv);
vector<vector<char>> tv1 = moveLeft(vt);
if(tv1.size() == 1) {
if(tv1[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
q.push(tv1);
}
vector<vector<char>> tv2_1 = rotateOne(vt);
vector<vector<char>> tv2 = moveLeft(tv2_1);
if(tv2.size() == 1) {
if(tv2[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv2 = rotateThree(tv2);
q.push(tv2);
}
vector<vector<char>> tv3_1 = rotateTwo(vt);
vector<vector<char>> tv3 = moveLeft(tv3_1);
if(tv3.size() == 1) {
if(tv3[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv3 = rotateTwo(tv3);
q.push(tv3);
}
vector<vector<char>> tv4_1 = rotateThree(vt);
vector<vector<char>> tv4 = moveLeft(tv4_1);
if(tv4.size() == 1) {
if(tv4[0][0] == 'O') {
answer = cnt;
into = 1;
}
}
else {
tv4 = rotateOne(tv4);
q.push(tv4);
}
}
}
if(into == 1)
return;
//3-4
qs = q.size();
solver(cnt + 1);
}
int main() {
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
t.clear();
answer = -1;
while(!q.empty()) {
q.pop();
}
point.clear();
scanf("%d %d", &N, &M);
t.resize(N);
for(i = 0; i < N; i++) {
for(j = 0; j < M; j++) {
char tmp;
//scanf("%c ", &tmp);
cin >> tmp;
t[i].push_back(tmp);
}
}
q.push(t);
qs = q.size();
solver(1);
printf("%d\n", answer);
}
return 0;
}