백준 6087번 : 레이저 통신 - 다익스트라 C++

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

6087번: 레이저 통신

 

 

 

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

int w, h;
int stx, sty, enx, eny;
int arr[101][101];
int dis[101][101];

int dx[4] = { -1, 0,1,0 };
int dy[4] = { 0, 1,0,-1 };

struct Node {
	int x, y, dist, direction;

	bool operator<(const Node& b) const {
		return dist > b.dist;
	}
};



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dis, 0x3f, sizeof(dis));

	cin >> w >> h;
	bool st = false;

	for (int i = 0; i < h; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < w; j++) {
			if (s[j] == '*') {
				arr[i][j] = -1;
			}
			else if (s[j] == 'C' && st == false) {
				stx = i;
				sty = j;
				st = true;
			}
			else if (s[j] == 'C' && st == true) {
				enx = i;
				eny = j;
			}
		}
	}


	priority_queue<Node> Q;

	dis[stx][sty] = 0;

	for (int i = 0; i < 4; i++) {
		int nx = stx + dx[i];
		int ny = sty + dy[i];

		if (nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny]==-1 ) continue;

		Q.push({ nx,ny,0,i });
	}


	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int dist = Q.top().dist;
		int direction = Q.top().direction;
		Q.pop();


		if (dis[x][y] < dist) continue;
		dis[x][y] = dist;

		if (x == enx && y == eny) {
			cout << dist << '\n';
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			if (abs(i - direction) == 2) continue;

			int nx = x + dx[i];
			int ny = y + dy[i];
			int nd = dist;
			if (i != direction) {
				nd++;
			}
			if (nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny] == -1) continue;
			if (dis[nx][ny] < nd) continue;
			Q.push({ nx,ny,nd,i });
		}
	}



	//for (int i = 0; i < h; i++) {
	//	for (int j = 0; j < w; j++) {
	//		if (dis[i][j] > 10) cout << '*';
	//		else cout << dis[i][j];
	//	}
	//	cout << '\n';
	//}


	return 0;
}

백준 6087번