백준 3055 탈출

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

3055번: 탈출

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;
int R, C;
char map[51][51];
int res;
int bix, biy, hedx, hedy, wax, way,stx,sty;
queue <pair<pair<int, int>,pair<int, char > > > q;
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};

void solve(int hx , int hy) {
	q.push(make_pair(make_pair(hx, hy),make_pair( 0,map[hx][hy])));

	while (!q.empty()) {

		int cx = q.front().first.first;
		int cy = q.front().first.second;
		int cnt = q.front().second.first; 
		char ch = q.front().second.second;
	 	q.pop();
		if (cx== bix && cy== biy) {
			res = cnt;
			return;
		}
		for (int i = 0; i < 4; i++) { //이동 
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (ch == '*') {
				if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
					if (map[nx][ny] != '*' && map[nx][ny] != 'X' && map[nx][ny] != 'D') {
						map[nx][ny] = '*';
						q.push(make_pair(make_pair(nx, ny), make_pair(cnt + 1,map[nx][ny])));
						
					}
				}
			}
			else if (ch == 'S') {
				if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
					if (map[nx][ny] != '*' && map[nx][ny] != 'X' && map[nx][ny] != 'S') {
						map[nx][ny] = 'S';
						q.push(make_pair(make_pair(nx, ny), make_pair(cnt + 1, map[nx][ny])));
					}
				}
			}

		}


	}

}
int main() {
	res = 987654321;

	scanf("%d%d", &R, &C);
	
	for (int i = 0; i < R; i++) {
			scanf("%s", map[i]);
		for (int j = 0; j < C; j++) {
			if (map[i][j] == 'D') {
				bix = i; biy = j;
			}
			else if (map[i][j] == 'S') {
				hedx = i; hedy = j;
			}
			else if (map[i][j] == '*') {
				q.push(make_pair(make_pair(i, j), make_pair(0, map[i][j])));
			}
		}
	}
	//res = 0;
	solve(hedx,hedy);
	
	if (res == 987654321) {
		printf("KAKTUS");
	}
	else {
		printf("%d", res);
	}


}