<유사문제>
13459 째로탈출 https://www.acmicpc.net/problem/13459 (성공여부만 판단)
BFS로 해결한다.
#include <cstdio>
#include <queue>
using namespace std;
class Point{
Point(){}
Point(int ny, int nx, int ncount, int nstate){
y = ny;
x = nx;
count = ncount;
state = nstate;
}
int y, x;
int count = 1, state = 0;
};
int N, M;
char arr[11][11];
Point blue, red, out;
int BFS(){
int i = 1, j = 1;
int ans;
queue<Point> B,R;
B.push(blue);
R.push(red);
while (!B.empty() && B.front().count <= 10){
Point b = B.front();
Point r = R.front();
B.pop(); R.pop();
//case <1> 왼쪽으로 기울일 경우
if (b.state != 2){
i = 1; j = 1;
while (arr[b.y][b.x - i] == '.'){
i++;
}
while (arr[r.y][r.x - j] == '.'){
j++;
}
if (i == 1 && j == 1){
if (arr[r.y][r.x - j] == 'O')
return r.count;
}
else if (i != 1 || j != 1){
if (arr[b.y][b.x - i] == '#' && arr[r.y][r.x - j] == '#'){ //둘다 막혀있는곳
if (b.y == r.y && b.x - i == r.x - j){
if (b.x < r.x){
B.push(Point(b.y, b.x - i + 1, b.count + 1, 1));
R.push(Point(r.y, r.x - j + 2, r.count + 1, 1));
}
else{
B.push(Point(b.y, b.x - i + 2, b.count + 1, 1));
R.push(Point(r.y, r.x - j + 1, r.count + 1, 1));
}
}
else{
B.push(Point(b.y, b.x - i + 1, b.count + 1, 1));
R.push(Point(r.y, r.x - j + 1, r.count + 1, 1));
}
}
else if (arr[b.y][b.x - i] == '#' && arr[r.y][r.x - j] == 'O'){ //빨강이 끝냈을 경우
return r.count;
}
}
}
//case <2> 오른쪽으로 기울일 경우
if (b.state != 1){
i = 1; j = 1;
while (arr[b.y][b.x + i] == '.'){
i++;
}
while (arr[r.y][r.x + j] == '.'){
j++;
}
if (i == 1 && j == 1){
if (arr[r.y][r.x + j] == 'O')
return r.count;
}
else if (i != 1 || j != 1){
if (arr[b.y][b.x + i] == '#' && arr[r.y][r.x + j] == '#'){ //둘다 막혀있는곳
if (b.y == r.y && b.x + i == r.x + j){
if (b.x > r.x){
B.push(Point(b.y, b.x + i - 1, b.count + 1, 2));
R.push(Point(r.y, r.x + j - 2, r.count + 1, 2));
}
else{
B.push(Point(b.y, b.x + i - 2, b.count + 1, 2));
R.push(Point(r.y, r.x + j - 1, r.count + 1, 2));
}
}
else{
B.push(Point(b.y, b.x + i - 1, b.count + 1, 2));
R.push(Point(r.y, r.x + j - 1, r.count + 1, 2));
}
}
else if (arr[b.y][b.x + i] == '#' && arr[r.y][r.x + j] == 'O'){ //빨강이 끝냈을 경우
return r.count;
}
}
}
if (b.state != 4){
//case <3> 위쪽으로 기울일 경우
i = 1; j = 1;
while (arr[b.y + i][b.x] == '.'){
i++;
}
while (arr[r.y + j][r.x] == '.'){
j++;
}
if (i == 1 && j == 1){
if (arr[r.y + j][r.x] == 'O')
return r.count;
}
else if (i != 1 || j != 1){
if (arr[b.y + i][b.x] == '#' && arr[r.y + j][r.x] == '#'){ //둘다 막혀있는곳
if (b.y + i == r.y + j && b.x == r.x){
if (b.y > r.y){
B.push(Point(b.y + i - 1, b.x, b.count + 1, 3));
R.push(Point(r.y + j - 2, r.x, r.count + 1, 3));
}
else{
B.push(Point(b.y + i - 2, b.x, b.count + 1, 3));
R.push(Point(r.y + j - 1, r.x, r.count + 1, 3));
}
}
else{
B.push(Point(b.y + i - 1, b.x, b.count + 1, 3));
R.push(Point(r.y + j - 1, r.x, r.count + 1, 3));
}
}
else if (arr[b.y + i][b.x] == '#' && arr[r.y + j][r.x] == 'O'){ //빨강이 끝냈을 경우
return r.count;
}
}
}
if (b.state != 3){
//case <4> 아래쪽으로 기울일 경우
i = 1; j = 1;
while (arr[b.y - i][b.x] == '.'){
i++;
}
while (arr[r.y - j][r.x] == '.'){
j++;
}
if (i == 1 && j == 1){
if (arr[r.y - j][r.x] == 'O')
return r.count;
}
else if (i != 1 || j != 1){
if (arr[b.y - i][b.x] == '#' && arr[r.y - j][r.x] == '#'){ //둘다 막혀있는곳
if (b.y - i == r.y - j && b.x == r.x){
if (b.y > r.y){
B.push(Point(b.y - i + 2, b.x, b.count + 1, 4));
R.push(Point(r.y - j + 1, r.x, r.count + 1, 4));
}
else{
B.push(Point(b.y - i + 1, b.x, b.count + 1, 4));
R.push(Point(r.y - j + 2, r.x, r.count + 1, 4));
}
}
else{
B.push(Point(b.y - i + 1, b.x, b.count + 1, 4));
R.push(Point(r.y - j + 1, r.x, r.count + 1, 4));
}
}
else if (arr[b.y - i][b.x] == '#' && arr[r.y - j][r.x] == 'O'){ //빨강이 끝냈을 경우
return r.count;
}
}
}
}
return -1;
}
int main(){
scanf("%d%d", &N, &M);
for (int n = 0; n < N; n++)
scanf("%s", arr[n]);
for (int n = 0; n < N; n++){
for (int m = 0; m < M; m++){
if (arr[n][m] == 'B'){
blue.y = n; blue.x = m;
arr[n][m] = '.';
}
else if (arr[n][m] == 'R'){
red.y = n; red.x = m;
arr[n][m] = '.';
}
else if (arr[n][m] == 'O'){
out.y = n; out.x = m;
}
}
}
printf("%d\n",BFS());
return 0;
}
| cs |
댓글 없음:
댓글 쓰기