[백준 5980] Corn Maze

문제

www.acmicpc.net/problem/5980

5980번: Corn Maze

 

문제 풀이

 

알파벳으로 입력받는 Transport해주는 점들의 좌표를 따로 관리해주며 그 점들 간의 이동시에는 0 코스트가 들기 때문에 방문처리를 하지 않도록 조심하며 bfs를 돌리면 됩니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const int dir[4][2] = { {-1,0}, {1,0}, {0,-1},{0,1} };
int r, c, cr, cc, nr, nc, dist;
char g[301][301];
bool vis[301][301];
pi st, fi;
vector<pi> tp[26];

void bfs() {
	queue<pair<pi, int>> q;
	q.push({ st,0 });
	vis[st.first][st.second] = 1;
	while (!q.empty()) {
		cr = q.front().first.first, cc = q.front().first.second, dist = q.front().second;
		q.pop();
		if (cr == fi.first && cc == fi.second) {
			cout << dist;
			return;
		}
		for (int i = 0; i < 4; i++) {
			nr = cr + dir[i][0], nc = cc + dir[i][1];
			if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
			if (!vis[nr][nc] && g[nr][nc] != '#') {
				if (isalpha(g[nr][nc])) {
					int d = g[nr][nc] - 'A';
					if (nr == tp[d][0].first && nc == tp[d][0].second)
						nr = tp[d][1].first, nc = tp[d][1].second;
					else 
						nr = tp[d][0].first, nc = tp[d][0].second;
				}
				else vis[nr][nc] = 1;
				q.push({ {nr,nc},dist + 1 });
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> g[i][j];
			if (g[i][j] == '=') fi = { i,j };
			else if (isalpha(g[i][j])) tp[g[i][j] - 'A'].push_back({ i,j });
			else if (g[i][j] == '@') st = { i,j };
		}
	}
	bfs();
}