백준14466 소가 길을 건너간 이유 6

작성일 | In

문제 링크

  • http://icpc.me/14466

문제 출처

  • USACO 2017 February Contest Silver 3번

풀이

다리를 건너지 않고 인접한 칸으로 이동해서 도착할 수 있는지 확인해주면 됩니다.
인접 리스트 + set 대신 인접 행렬로 구현해도 됩니다.

전체 코드

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
49
50
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
set<p> g[111][111];
int n, k, r;

int di[] = {0, 0, 1, -1};
int dj[] = {1, -1, 0, 0};
int visit[111][111];

void dfs(int i, int j){
	if(i < 1 || i > n || j < 1 || j > n) return;
	visit[i][j] = 1;
	for(int x=0; x<4; x++){
		int ii = i + di[x];
		int jj = j + dj[x];
		if(!visit[ii][jj] && !g[i][j].count({ii, jj})){
			dfs(ii, jj);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> r;

	for(int i=0; i<r; i++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		g[a][b].insert({c, d});
		g[c][d].insert({a, b});
	}

	vector<p> v(k);
	for(int i=0; i<k; i++){
		cin >> v[i].first >> v[i].second;
	}

	int ans = 0;
	for(int i=0; i<k; i++){
		memset(visit, 0, sizeof visit);
		dfs(v[i].first, v[i].second);
		for(int j=i+1; j<k; j++){
			if(!visit[v[j].first][v[j].second]){
				ans++;
			}
		}
	}
	cout << ans;
}