本文共 2942 字，大约阅读时间需要 9 分钟。

$$WhyDidtheCowCrosstheRoadIG$$

题目链接： / /

题目

奶牛们为什么要穿马路？一个原因只是因为$FJ$的牧场的路实在是太多了，使得奶牛们每天不得不穿梭在许许多多的马路中央

$FJ$的牧场可以看作是一块 $N\times N$ 的田地$（3\le N\le 100）$，$N-1$ 条南北向的道路和 $N-1$ 条东西向的道路贯穿整个牧场，同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。$Bessie$只要穿过分离两块田野的道路，就可以从任何田野移动到与其相邻的田野里去（北，东，南或西）。当然，$Bessie$穿过每一条马路都是需要TT 时间的。$（0\le T\le 1,000,000）$

有一天，$FJ$邀请$Bessie$来他家下棋，$Bessie$从牧场的西北角出发，$FJ$的家在牧场的东南角。因为$Bessie$在中途可能会饿，所以她每走过三块田野就要停下来，享用她所在田野上的新鲜的牧草（不包括$Bessie$的出发点，但是可能会包括终点$FJ$的家），牧场上有些田野的牧草长得比其他地方茂盛，所以$Bessie$对应的停留时间也会变长。

请帮帮$Bessie$计算出她走到$FJ$家的最短时间。

输入

接下来 $N$ 行，每行 $N$ 个数表示每块田野$Bessie$需要停留的时间（每块最多不超过$100,000$），第一行的第一块田野是牧场的西北角

输出

一行一个整数表示$Bessie$走到$FJ$家的最短时间

样例输入

4 230 92 36 1038 85 60 1641 13 5 6820 97 13 80

样例输出

31

样例解释

对于样例，$Bessie$先向东走过了三块田野（在$“10”$停留），再向南走两步，又向西走了一步（在$“5”$停留），最后向南走一步，再向东走一步到达$FJ$的家（不用停留），总共时间是$15$（停留时间）+$16$（穿马路时间）=$31$

思路

这道题其实就是一道最短路。

因为题目说每走$3$部就要吃草，那我们就让它三步三步的走，把从一个点走三步可以走到的地方连起来就完事了。

具体看代码吧。

代码

#include
   
    #include
    
     #include
     
      using namespace std;struct node {   	int x, y;};int n, t, a[101][101], dis[101][101], ans;bool in[101][101];int dx[16] = {   0, 0, 3, -3, 1, 1, 2, 2, -1, -1, -2, -2, 0, 0, 1, -1};int dy[16] = {   3, -3, 0, 0, 2, -2, 1, -1, 2, -2, 1, -1, 1, -1, 0, 0};bool ch(int x, int y) {   	if (x < 1 || y < 1 || x > n || y > n) return 0;	return 1;}void spfa(int x, int y) {   //最短路	queue
      
       q;	q.push((node){   x, y});	memset(dis, 0x7f, sizeof(dis));	dis[x][y] = 0;	in[x][y] = 1;	while (!q.empty()) {   		node now = q.front();		q.pop();		in[now.x][now.y] = 0;		for (int i = 0; i < 16; i++) {   			int tx = now.x + dx[i], ty = now.y + dy[i];			if (ch(tx, ty) && dis[now.x][now.y] + a[tx][ty] + 3 * t < dis[tx][ty]) {   //记得要加上走路的时间				dis[tx][ty] = dis[now.x][now.y] + a[tx][ty] + 3 * t;				if (!in[tx][ty]) {   					in[tx][ty] = 1;					q.push((node){   tx, ty});				}			}		}	}}int main() {   //	freopen("visitfj.in", "r", stdin);//	freopen("visitfj.out", "w", stdout);		scanf("%d %d", &n, &t);//读入	for (int i = 1; i <= n; i++)		for (int j = 1; j <= n; j++)			scanf("%d", &a[i][j]);//读入		spfa(1, 1);//最短路		ans = min(dis[n][n], dis[n - 1][n] + t);//租后一步是怎么走到终点的（指不用吃草的时候）	ans = min(ans, dis[n][n - 1] + t);	ans = min(ans, dis[n - 2][n] + t * 2);	ans = min(ans, dis[n][n - 2] + t * 2);	ans = min(ans, dis[n - 1][n - 1] + t * 2);		printf("%d", ans);//输出	//	fclose(stdin);//	fclose(stdout);		return 0;}