백준 15653번 : 구슬 탈출 4 , C++ 문제풀이 코드

https://www.acmicpc.net/problem/15653

15653번: 구슬 탈출 4

 

 

기존 구슬 탈출 문제 풀이 및 설명

https://dingcoding.tistory.com/86

백준 13459번 : 구슬 탈출 - BFS C++ 문제풀이코드

 

BFS 제한 조건만 조금 바꿔주면 동일한 문제다.

 

C++ 문제풀이 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
char arr[15][15];
bool ch[15][15][15][15], isend;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

struct Ball {
	int rx, ry, bx, by, trial;
	Ball(int a, int b, int c, int d, int e) {
		rx = a;
		ry = b;
		bx = c;
		by = d;
		trial = e;
	}
};


void move(int &nrx, int &nry, int dx, int dy, int &cnt) {
	while (1) {
		if (arr[nrx][nry] == '#') {
			nrx -= dx;
			nry -= dy;
			cnt--;
			break;
		}
		if (arr[nrx][nry] == 'O') {
			break;
		}
		nrx += dx;
		nry + dy;
		cnt++;
	}
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int rx1, ry1, bx1, by1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'R') {
				rx1 = i;
				ry1 = j;
			}
			else if (arr[i][j] == 'B') {
				bx1 = i;
				by1 = j;
			}
		}
	}

	queue<Ball> Q;
	ch[rx1][ry1][bx1][by1] = 1;
	Q.push(Ball(rx1, ry1, bx1, by1, 0));


	while (!Q.empty()) {
		int rx = Q.front().rx;
		int ry = Q.front().ry;
		int bx = Q.front().bx;
		int by = Q.front().by;
		int trial = Q.front().trial;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			// 다음 빨간공과 다음 파란공의 좌표, cnt는 이동 거리 
			int nrx = rx, nry = ry, rcnt = 0;
			int nbx = bx, nby = by, bcnt = 0;

			//공 기울이기 
			move(nrx, nry, dx[i], dy[i], rcnt);
			move(nbx, nby, dx[i], dy[i], bcnt);

			
			if (arr[nbx][nby] == 'O') continue;
			else if (arr[nrx][nry] == 'O') {
				cout << trial + 1;
				isend = true;
				return 0;
			}
			else {
				//기울였는데 공이 겹친 경우 더 멀리서 온 공을 덜 이동시켜야된다
				if (nrx == nbx && nry == nby) {
					if (rcnt > bcnt) {
						nrx -= dx[i];
						nry -= dy[i];
					}
					else {
						nbx -= dx[i];
						nby -= dy[i];
					}
				}

				if (ch[nrx][nry][nbx][nby] == 0) {
					ch[nrx][nry][nbx][nby] = 1;
					Q.push(Ball(nrx, nry, nbx, nby, trial + 1));
				}
			}
		}
	}

	if (!isend) {
		cout << -1;
	}


}