백준알고리즘
구슬탈출2
먼지의삶
2019. 8. 6. 00:54
#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로 판단하고 리턴시키는과정이포함되있고 처음에 인자로 함수를 정의 안했는데, 이렇게 안하면 맵이 굉장히 혼란스러워져서 그냥 인자로 함수를 구성했다.