문제: icpc.me/13460
빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다.
우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <cstdio> #include <algorithm> #include <queue> using namespace std; int n, m, disc[11][11][11][11], bx, by, rx, ry; char a[11][11]; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int bfs() { queue<pair<pair<int, int>, pair<int,int>>> qu; qu.push({ {rx,ry},{bx,by} }); disc[rx][ry][bx][by] = 1; int ret = 0; while (qu.size()) { int qs = qu.size(); while (qs--) { int x = qu.front().first.first; int y = qu.front().first.second; int z = qu.front().second.first; int w = qu.front().second.second; qu.pop(); if (a[x][y] == 'O'&&a[x][y] != a[z][w]) return ret; for (int i = 0; i < 4; i++) { int cx = x, cy = y, cz = z, cw = w; while (a[cx + dx[i]][cy + dy[i]] != '#'&&a[cx][cy] != 'O') { cx += dx[i]; cy += dy[i]; } while (a[cz + dx[i]][cw + dy[i]] != '#'&&a[cz][cw] != 'O') { cz += dx[i]; cw += dy[i]; } if (cx == cz&&cy == cw) { if (a[cx][cy] == 'O')continue; if (abs(cx - x) + abs(cy - y) < abs(cz - z) + abs(cw - w)) { cz -= dx[i]; cw -= dy[i]; } else { cx -= dx[i]; cy -= dy[i]; } } if (disc[cx][cy][cz][cw])continue; qu.push({ {cx,cy} ,{cz,cw} }); disc[cx][cy][cz][cw] = 1; } } if (ret == 10) return -1; ret++; } return -1; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { getchar(); for (int j = 0; j < m; j++) { scanf("%c", &a[i][j]); if (a[i][j] == 'B') { bx = i; by = j; } else if (a[i][j] == 'R') { rx = i; ry = j; } } } printf("%d\n", bfs()); return 0; } | cs |
'알고리즘 관련 > BOJ' 카테고리의 다른 글
| BOJ)1058 친구 (0) | 2017.04.03 |
|---|---|
| BOJ)12100 2048 (Easy) (0) | 2017.03.30 |
| BOJ)13460 구슬탈출2 (6) | 2017.03.30 |
| BOJ)1520 내리막 길 (0) | 2017.03.30 |
| BOJ)10422 괄호 (0) | 2017.03.30 |
| BOJ)1194 달이 차오른다, 가자. (0) | 2017.03.30 |
와..본것중에 제일 깔끔해요!! 많이 배워갑니다 감사합니다:)
감사합니다 !! ..
진짜 코드 완전 이해하기 좋은 거 같아요 많이 배워갑니다!! :)
제일 깔끔!!
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
char map[10][10] = { 0, };
int ans;
int Min = 11;
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int hx, hy;
void go(int cnt, int pre, int rx, int ry, int bx, int by) {
int r_ch = 0, b_ch = 0; //빨간공과 파란공이 구멍에 들어간 경우 1로 초기화
int i, j;
int n_rx, n_ry, n_bx, n_by;
//최소를 넘기면 리턴
if (cnt >= Min) //이미 구해진 최소보다 크다면 더 구할 필요 없다.
return;
//****************우선순위!!!!!!!
//움직임 명령에 따라 빨간공과 파란공 움직임.
n_rx=rx, n_ry=ry, n_bx=bx, n_by=by;
while (1) {
if (map[n_rx + dx[pre]][n_ry + dy[pre]] == '#') {
break;
}
else {
n_rx = n_rx + dx[pre];
n_ry = n_ry + dy[pre];
}
if (n_rx == hx && n_ry == hy) {
r_ch = 1; //빨간공이 구멍에 들어감}
break; //반복문 탈출
}
}
while (1) {
if (map[n_bx + dx[pre]][n_by + dy[pre]] == '#') {
break; //만약 벽이라면 반복문 탈출
}
else {
n_bx = n_bx + dx[pre];
n_by = n_by + dy[pre];
}
if (n_bx == hx && n_by == hy)
b_ch = 1; //빨간공이 구멍에 들어감
}
if (b_ch == 1) //빨간공과 함께 파란공이 들어간 경우와 파란공 혼자 들어간 경우 모두 false
return;
else if (r_ch == 1) {//빨간공만 들어간 경우
Min = min(Min, cnt); //최솟값인지 확인후 리턴
return;
}
if (n_rx == n_bx && n_ry == n_by) { //같은 위치에 있는경우
if (abs(rx - n_rx) + abs(ry - n_ry) > abs(bx - n_bx) + abs(by - n_by)) { //더 많이 움직인 애가 위치를 바꿔야 한다.
n_rx -= dx[pre];
n_ry -= dy[pre];
}
else {
n_bx -= dx[pre];
n_by -= dy[pre];
}
}
rx = n_rx, ry = n_ry, bx = n_bx, by = n_by;
if (pre == 0 || pre == 1) {
go(cnt + 1, 2,rx,ry,bx,by);
go(cnt + 1, 3, rx, ry, bx, by);
}
else if (pre == 2 || pre == 3) {
go(cnt + 1, 0, rx, ry, bx, by);
go(cnt + 1, 1, rx, ry, bx, by);
}
}
int main() {
cin >> n >> m;
int rx, ry, bx, by;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 'B')
bx = i, by = j;
else if (map[i][j] == 'R')
rx = i, ry = j;
else if (map[i][j] == 'O')
hx = i, hy = j;
}
}
go(1, 0, rx, ry, bx, by);
go(1, 1, rx, ry, bx, by);
go(1, 2, rx, ry, bx, by);
go(1, 3, rx, ry, bx, by);
if (Min == 11)
cout << -1;
else
cout << Min;
//system("pause");
}
저는 DFS로 풀어봤어요
덕분에 겹치는 부분에서 어케 해결해야할지 고민이였는데
너무 쉽게 코딩해주셔서 많은 도움이 됐어요!!
감사합니다.
깔끔한 코드에 감동 받고 갑니닷