题目描述
(S)国的动物园是一个(N*M)的网格图，左上角的坐标是((1,1))，右下角的坐标是((N,M))。小象在动物园的左上角，它想回到右下角的家里去睡觉，但是动物园中有一些老鼠，而小象又很害怕老鼠。动物园里的老鼠是彼此互不相同的。小象的害怕值定义为他回家的路径上可以看见的不同的老鼠的数量。若小象当前的位置为((x1,y1))，小象可以看见老鼠，当且仅当老鼠的位置((x2,y2))满足(|x1-x2|+|y1-y2|<=1)。由于小象很困了，所以小象只会走一条最近的路回家，即小象只会向下或者向右走。现在你需要帮小象确定一条回家的路线，使得小象的害怕值最小。
输入格式
第一行包含两个用空格隔开的整数，(N)和(M)。
接下来一个(N*M)的矩阵表示动物园的地图。其中(A[i][j])表示第(i)行第(j)列上老鼠的数量。若(A[i][j]=0)则表示当前位置上没有老鼠(小象的家里也可能存在老鼠)。
输出格式
输出一个整数，表示路线最小的害怕值是多少。
样例
样例输入
3 9
0 0 1 0 0 0 0 0 1
1 1 1 1 1 1 0 1 0
1 0 0 1 0 0 1 0 0
样例输出
9
code
#include <bits/stdc++.h>
using namespace std;
//动物园里的老鼠是彼此互不相同的。小象的害怕值定义为他回家的路径上可以看见的不同的老鼠的数量。！！！
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn][2]; // 0从左方转移，1从上边转移
int a[maxn][maxn];
int main() {
memset(dp, INF, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
dp[1][1][1] = a[1][1] + a[1][2] + a[2][1]; //自己家里的+下方的+右边的
dp[1][1][0] = a[1][1] + a[1][2] + a[2][1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (i == 1)
dp[i][j][0] = min(dp[i][j - 1][1], dp[i][j - 1][0]) + a[i + 1][j] + a[i][j + 1];
else if (j == 1)
dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i + 1][j] + a[i][j + 1];
else {
dp[i][j][1] = min(dp[i - 1][j][0], dp[i - 1][j][1] + a[i][j - 1]) + a[i + 1][j] + a[i][j + 1];
//如果f[i][j]的上一个点(即f[i-1][j][0])为左边即f[i-1][j-1]转移来的，那么直接转移即可，
//因为左边f[i][j-1]这种老鼠已经见过了，画图理解
//如果f[i][j]的上一个点(即f[i-1][j][1])为上边即f[i-2][j]转移来的，那么因为左边f[i][j-1]这种老鼠没见过，
//所以需要在加上左边f[i][j-1]这种老鼠
dp[i][j][0] = min(dp[i][j - 1][1], dp[i][j - 1][0] + a[i - 1][j]) + a[i + 1][j] + a[i][j + 1];
//动物园里的老鼠是彼此互不相同的。小象的害怕值定义为他回家的路径上可以看见的不同的老鼠的数量。！！！
}
}
return cout << min(dp[n][m][0], dp[n][m][1]) << endl, 0;
}