9944번: NxM 보드 완주하기
문제 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다. 게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다. 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로
www.acmicpc.net
/* 1시간 55분 이상 소요 */
/* 1. map의 첫번째 칸은 이미 입력됐으므로 두번째 칸부터 입력받기, row는 첫번째 칸부터 참조 */
/* 2. if(map)의 역할을 while(map)이 대신해줄거라 생각했지만 map이 1이면 while의 body 이후도 실행되면 안되기 때문에 if로 continue해준다. */
/* 3. 탐색 시 첫번째 위치 처리 해주기! 방문 처리 및 빈칸 카운터 increment */
/* 4. 마지막 input이 빈줄일 경우의 예외처리 */
#include <iostream>
#include <string>
#include <string.h>
#define loop(x, b, e) for(int x = (b); x < (e); ++x)
using namespace std;
int N, M;
bool map[32][32];
int es[900][2], en;
int md = 10000;
const int dn[] = { -1, 0, 1, 0 };
const int dm[] = { 0, 1, 0, -1 };
void DFS(int n, int m, int d, int ei) {
if (d > md)
return;
if (ei == en) {
if (d < md) md = d;
return;
}
loop(dr, 0, 4) {
int cn = n + dn[dr], cm = m + dm[dr];
if (map[cn][cm]) /* 2 */
continue;
int cei = ei;
while (!map[cn][cm]) {
map[cn][cm] = 1;
++cei;
cn += dn[dr], cm += dm[dr];
}
cn -= dn[dr], cm -= dm[dr];
DFS(cn, cm, d + 1, cei);
while (cn != n || cm != m) {
map[cn][cm] = 0;
cn -= dn[dr], cm -= dm[dr];
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
memset(map[0], 1, 32);
loop (n, 0, 32) map[n][0] = 1;
for(int tc = 1; !cin.eof(); ++tc) {
cin >> N >> M; cin.get();
loop(n, 1, N + 1) {
string row; getline(cin, row);
if (row == "") return 0; /* 4 */
loop(m, 0, M)
if (row[m] == '*') map[n][m + 1] = 1; /* 1 */
else { es[en][0] = n; es[en++][1] = m + 1; } /* 1 */
map[n][M + 1] = 1;
}
memset(map[N + 1], 1, M + 2);
loop(ei, 0, en) {
map[es[ei][0]][es[ei][1]] = 1; /* 3 */
DFS(es[ei][0], es[ei][1], 0, 1); /* 3 */
map[es[ei][0]][es[ei][1]] = 0; /* 3 */
}
if (md == 10000) md = -1;
cout << "Case " << tc << ": " << md << '\n';
loop(n, 1, N + 2) memset(map[n] + 1, 0, M + 1);
en = 0;
md = 10000;
}
return 0;
}