[정올 1082] 화염에서탈출(SLIKAR)

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=99 

JUNGOL

#include <stdio.h>

int R, C, s, e, dr[4] = { 0,0,1,-1 }, dc[4] = { 1,-1,0,0 }, ans;
char grid[55][55];
struct P {
	int r, c, cnt;
	char type;
} que[10000];

void enq(int r, int c, int cnt, char type) {
	que[e].r = r, que[e].c = c, que[e].cnt = cnt, que[e++].type = type;
	grid[r][c] = type;
}
P deq() { return que[s++]; }

bool check(int r, int c, char curtype) {
	if (r < 0 || c < 0 || r >= R || c >= C) return false;
	if (curtype == '*') {  
		//가려는 곳이 S나 .이면 번지고, X나 D나 *이면 번지지 않는다.
		if (grid[r][c] == 'S' || grid[r][c] == '.') return true;
		else return false;
	}
	else {//(curtype == 'S')
		//가려는 곳이 .이면 번지고, D면 끝내고, *이나 X면 번지지 않는다.
		if (grid[r][c] == 'D' || grid[r][c] == '.') return true;
		else return false;
	}
}
void BFS() {
	P cur;
	int newr, newc;
	while (s < e) {
		cur = deq();
		//같은 시간에 S와 *이 겹치면 *이 우선하므로, 그런 경우
		if (cur.type == 'S' && grid[cur.r][cur.c] == '*') continue; 
		for (int i = 0; i < 4; i++) {
			newr = cur.r + dr[i], newc = cur.c + dc[i];
			if (check(newr, newc, grid[cur.r][cur.c])) {
				if (cur.type == 'S' && grid[newr][newc] == 'D') { ans = cur.cnt + 1; return; }
				enq(newr, newc, cur.cnt + 1, grid[cur.r][cur.c]);
			}
		}
	}
}
int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d%d", &R, &C);
	for (int r = 0; r < R; r++) {
		scanf("%s", grid[r]);
		//S를 먼저 넣고, *은 나중에 넣는다.
		for (int c = 0; c < C; c++) if (grid[r][c] == 'S') enq(r, c, 0, 'S'); 
	}
	for (int r = 0; r < R; r++) 
		for (int c = 0; c < C; c++) if (grid[r][c] == '*') enq(r, c, 0, '*');
	BFS();
	if (ans) printf("%d\n", ans);
	else printf("impossible\n");

	return 0;
}