[题解]vistifj

发表于 | 评论数： | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 2 分钟

题目描述

题解

一种显然的做法是$dfs$枚举所有路线，但这样时间复杂度爆炸。注意到$n<=100$，考虑记忆化，记录$dp[i][j][3]$表示到坐标$(i,j)$走了$s$ $mod$ $3$所需的最小花费。

一个小优化是将$dfs$改为像$bfs$的搜索，优先拓展花费小的状态。

Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
 
inline int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}
 
long long n , t ;
long long ans = INT_MAX ;
long long dp[110][110][3] , v[110][110], minx = INT_MAX;
const int dx[] = {1, -1, 0, 0},
		  dy[] = {0, 0, 1, -1};
bool vis[110][110];
 
inline long long Min(long long a , long long b)
{
	return a < b? a : b;
}
 
struct node{
	int x , y;
	long long tot;
	int s;
	bool operator <(const node &x) const {return x.tot < tot;}
};
 
inline void bfs()
{
	priority_queue<node> q;
	q.push((node){1 , 1 , 0});
	while(!q.empty())
	{
		node k = q.top();
		q.pop();
		if(k.tot >= dp[k.x][k.y][k.s % 3]) continue;
		dp[k.x][k.y][k.s % 3] = k.tot;
		if(k.tot >= ans) continue;
		if(k.x == n and k.y == n) {
			ans = k.tot;
			continue;
		} 
		for(int i = 0; i < 4; i ++)
		{
			int xx = k.x + dx[i] , yy = k.y + dy[i] , ss = k.s + 1;
			if(xx < 1 or xx > n or yy < 1 or yy > n) continue;
			q.push(node{xx , yy , k.tot + t + (ss % 3 == 0) * v[xx][yy] , ss});
		}
	}
}
 
int main()
{
	n = read() , t = read();
	for(register int i = 1; i <= n; i ++)
	  for(register int j = 1; j <= n; j ++) 
	    v[i][j] = read();
	for(register int i = 1; i <= n; i ++) for(register int j = 1; j <= n; j ++) for(register int k = 0; k < 3; k ++) dp[i][j][k] = INT_MAX;
	bfs();
    printf("%d\n" , ans);
	return 0;
}