백준14461 소가 길을 건너간 이유 7

작성일 | In

문제 링크

  • http://icpc.me/14461

문제 출처

  • USACO 2017 February Contest Gold 1번

풀이

3번 이동할 때 마다 풀을 먹습니다.
3번 이동하는 경우는 A에서 B, C, D로 이동하는 것처럼 3만큼 떨어진 곳으로 이동하거나, A에서 B, C, B로 이동하는 것처럼 1만큼 떨어진 곳으로 이동하는 경우가 있습니다. dx, dy를 아래와 같이 작성합시다.

1
2
const int dx[] = {1, -1,  0,  0,  0,  1,  2,  3,  2,  1,  0, -1, -2, -3, -2, -1};
const int dy[] = {0,  0,  1, -1,  3,  2,  1,  0, -1, -2, -3, -2, -1,  0,  1,  2};

격자에서 다익스트라를 돌려주면서 최단 비용을 구해주면 됩니다.
자세한 구현 방법은 아래 코드의 주석을 참고하시면 됩니다.

전체 코드

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

const int dx[] = {1, -1,  0,  0,  0,  1,  2,  3,  2,  1,  0, -1, -2, -3, -2, -1};
const int dy[] = {0,  0,  1, -1,  3,  2,  1,  0, -1, -2, -3, -2, -1,  0,  1,  2};

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

int arr[100][100];
int dist[100][100];
int n, t;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> t;
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> arr[i][j];
	memset(dist, 0x3f, sizeof dist);
	dist[0][0] = 0;
	priority_queue<p> pq;
	pq.push({0, 0});

	int ans = 1e9+103;
	while(pq.size()){
		int cost = -pq.top().first;
    //int to coord
		int i = pq.top().second / n;
		int j = pq.top().second % n;
		pq.pop();
		if(dist[i][j] != cost) continue;

		int toN = (n-i-1) + (n-j-1);
    //목적지까지 거리가 2 이하로 남았다면
		if(toN <= 2){
			ans = min(ans, cost + toN * t);
		}

		for(int k=0; k<16; k++){
			int ii = i + dx[k];
			int jj = j + dy[k];
			int nxtCost = cost + 3 * t + arr[ii][jj];
			if(ii < 0 || jj < 0 || ii >= n || jj >= n) continue;
			if(dist[ii][jj] < nxtCost) continue;
			dist[ii][jj] = nxtCost;
			pq.push({-dist[ii][jj], ii*n + jj/*coord to int*/});
		}
	}
	cout << ans;
}