백준2423 전구를 켜라

작성일 | In

문제 링크

  • http://icpc.me/2423

문제 출처

  • 2011 BalticOI Day1 3번

사용 알고리즘

  • 다익스트라

시간복잡도

  • $NM \log (NM)$

풀이

간단한 다익스트라(또는 01 BFS) 문제입니다.
교육용으로 좋을 것 같습니다.

각 꼭짓점을 정점으로 잡고, 서로 대각선 방향으로 마주보고 있는 두 정점을 가중치가 0 또는 1인 간선으로 연결해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

inline int id(int i, int j){ return i*555+j; }

int n, m; char a[555][555];
vector<p> g[303030];
int dst[303030];

void addEdge(int s, int e, int x){
	g[s].emplace_back(e, x);
	g[e].emplace_back(s, x);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> a[i][j];
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
		if(a[i][j] == '/'){
			addEdge(id(i-1, j-1), id(i, j), 1);
			addEdge(id(i-1, j), id(i, j-1), 0);
		}
		else{
			addEdge(id(i-1, j-1), id(i, j), 0);
			addEdge(id(i-1, j), id(i, j-1), 1);
		}
	}

	memset(dst, 0x3f, sizeof dst);
	priority_queue<p> pq; pq.emplace(0, id(0, 0)); dst[id(0, 0)] = 0;
	while(pq.size()){
		int now = pq.top().y, cst = -pq.top().x; pq.pop();
		if(cst > dst[now]) continue;
		for(auto i : g[now]) if(dst[i.x] > cst + i.y){
			dst[i.x] = cst + i.y; pq.emplace(-dst[i.x], i.x);
		}
	}
	int res = dst[id(n, m)];
	if(res < 1e9) cout << res;
	else cout << "NO SOLUTION";
}