구슬탈출2

#include<iostream>

using namespace std;

int h, w;
int map[10][10];
struct ball {
	int x, y;
	bool in = true;
};
ball r;
ball b;
int ans = 11;


void go(int dir, int cnt, int rx, int ry, int bx, int by) {//1은 아래로 2는 위로 3은 오른쪽으로 4는 왼쪽으루
	if (ans <= cnt) return;
	r.in = true; b.in = true;
	map[rx][ry] = 1; map[bx][by] = 2;
	bool mr = false; bool mb = false;
	bool rin = true; bool bin = true;
	
	if (dir == 1) {

			for (int i = 1; i < h - 1; i++) {
				if (rx > bx) {
					if (map[rx + 1][ry] == 3) {
						map[rx][ry] = 0;
						rin = false;
						mr = true;
					}
					if (map[rx + 1][ry] == 0) {
						map[rx][ry] = 0;
						rx += 1;
						map[rx][ry] = 1;
						mr = true;
					}
					if (map[bx + 1][by] == 0) {
						map[bx][by] = 0;
						bx += 1;
						map[bx][by] = 2;
						mb = true;
					}
					if (map[bx + 1][by] == 3) {
						map[bx][by] = 0;
						bin = false;
						mb = true;
					}
				}
				else {
					if (map[rx + 1][ry] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[bx + 1][by] == 0) {
						map[bx][by] = 0;
						bx += 1;
						map[bx][by] = 2; mb = true;
					}
					if (map[rx + 1][ry] == 0) {
						map[rx][ry] = 0;
						rx += 1; mr = true;
						map[rx][ry] = 1;
					}
					if (map[bx + 1][by] == 3) {
						map[bx][by] = 0;
						bin = false; mb = true;

					}
				}
			}
		
	}

	if (dir == 2) {
			for (int i = 1; i < h - 1; i++) {
				if (r.x < b.x) {
					if (map[rx - 1][ry] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[rx - 1][ry] == 0) {
						map[rx][ry] = 0;
						rx -= 1; mr = true;
						map[rx][ry] = 1;
					}
					if (map[bx - 1][by] == 0) {
						map[bx][by] = 0;
						bx -= 1;
						map[bx][by] = 2; mb = true;
					}
					if (map[bx - 1][by] == 3) {
						map[bx][by] = 0;
						bin = false;
						mb = true;
					}
				}
				else {
					if (map[rx - 1][ry] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[bx - 1][by] == 0) {
						map[bx][by] = 0;
						bx -= 1;
						map[bx][by] = 2; mb = true;
					}
					if (map[rx - 1][ry] == 0) {
						map[rx][ry] = 0;
						rx -= 1; mr = true;
						map[rx][ry] = 1;
					}
					
					if (map[bx - 1][by] == 3) {
						map[bx][by] = 0;
						bin = false; mb = true;
					}
				}
			}
		
	}

	if (dir == 3) {
	
			for (int i = 1; i < w - 1; i++) {
				bool hole = false;
				if (ry > by) {

					if (map[rx][ry + 1] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[rx][ry + 1] == 0) {
						map[rx][ry] = 0; mr = true;
						ry += 1;
						map[rx][ry] = 1;
					}
					if (map[bx][by + 1] == 3) {
						map[bx][by] = 0;
						bin = false; mb = true;
					}
					if (map[bx][by + 1] == 0) {
						map[bx][by] = 0; 
						by += 1;
						map[bx][by] = 2; mb = true;
					}
					
				}
				else {
					
					if (map[bx][by+1] == 0) {
						map[bx][by] = 0;
						by += 1; mb = true;
						map[bx][by] = 2;
					}
					if (map[bx][by + 1] == 3) {
						map[bx][by] = 0;
						bin = false; mb = true;

					}
					if (map[rx][ry + 1] == 0) {
						map[rx][ry] = 0;
						ry += 1;
						map[rx][ry] = 1; mr = true;
					}
		
					if (map[rx][ry + 1] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
				}
			}
		
	}

	if (dir == 4) {
		
			for (int i = 1; i < w - 1; i++) {
				if (ry < by) {
					if (map[rx][ry - 1] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[rx][ry - 1] == 0) {
						map[rx][ry] = 0;
						ry -= 1; mr = true;
						map[rx][ry] = 1;
					}
					if (map[bx][by - 1] == 0) {
						map[bx][by] = 0; mb = true;
						by -= 1;
						map[bx][by] = 2;
					}
					if (map[bx][by - 1] == 3) {
						map[bx][by] = 0;
						mb = true;
						bin = false;
					}
				}
				else {
					if (map[rx][ry - 1] == 3) {
						map[rx][ry] = 0;
						rin = false; mr = true;
					}
					if (map[bx][by - 1] == 0) {
						map[bx][by] = 0;
						by -= 1; mb = true;
						map[bx][by] = 2;
					}
					if (map[rx][ry - 1] == 0) {
						map[rx][ry] = 0;
						ry -= 1;
						map[rx][ry] = 1; mr = true;
					}
					if (map[bx][by - 1] == 3) {
						map[bx][by] = 0; mb = true;
						bin = false;
					}
				}
			}
		
	}
	if (dir != 0) {
		if (mr == false && mb == false) {
			map[rx][ry] = 0; map[bx][by] = 0;
			return;
		}
	}
	/*cout << endl;

	cout << dir << endl;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}*/
	
	
	if (bin == false) { map[rx][ry] = 0; map[bx][by] = 0; return; }

	if (!rin) {
		if (ans > cnt) ans = cnt;
		map[rx][ry] = 0; map[bx][by] = 0;
		return;
	}

	for (int i = 1; i <= 4; i++) {
		map[rx][ry] = 1; map[bx][by] = 2;
		go(i, cnt+1,rx,ry,bx,by);
		map[rx][ry] = 0; map[bx][by] = 0;
	}
	//map[rx][ry] = 0; map[bx][by] = 0;
	
}

int main() {
	cin >> h >> w;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char x;
			cin >> x;
			//cout << x << endl;
			if (x == '#') {
				map[i][j] = 4;
			}
			if (x == '.')
				map[i][j] = 0;
			if (x == 'R')
			{
				//map[i][j] = 1;
				r.x = i;
				r.y = j;

			}
			if (x == 'B') {
				//map[i][j] = 2;
				b.x = i;
				b.y = j;
			}
			if (x == 'O')
				map[i][j] = 3;
		}
	}
	
	
	go(0, 0,r.x,r.y, b.x, b.y);
	
	if (ans == 11)
		cout << -1 << endl;
	else
		cout << ans << "\n";
	return 0;



}

방향마다 움직임제어 함수내부에서 백트래킹실행

만약, 아무것도 움직이지 않는경우라면 어차피 거기서 더이상 하는것은 쓸모가없다고 판단해서 bool로 판단하고 리턴시키는과정이포함되있고 처음에 인자로 함수를 정의 안했는데, 이렇게 안하면 맵이 굉장히 혼란스러워져서 그냥 인자로 함수를 구성했다.