题目大意

一个矩阵，每个元素均为0或1，要求从左上角到右下角的路径中，走过的格子和上下左右四个格子的1最少，输出1的个数（只能向下或右走）

思路

 从左上角到右下角的最少一的个数，这明显是一个DP题，那就应该推导DP转移方程了，首先，一个点应该有两种情况，从左边来或从上边来，因此数组应有1维是方向，而剩下还要两维是这个点的位置。

 但是预处理也是有点门道的，我在开始预处理的时候想的是在当前点上下左右的都加起来，但是写完以后发现答案要大好多，仔细分析一下，我们可以发现几个特点：

 1、当前点由左边或上边转移而来，所以左边或上边已经能够看到当前点的左边和上边的点，所以只需要预处理该点下和右边的数量。

 2、当前点是从左或上转移而来，如果上边的点仍然从上边转移来，那么该点的左边一定是没有统计过的，而从左边转移来的点上一次转移还是左边也是一样的，该点上边的点一定没有统计，所以我们就需要第三维来记录从左还是上转移而来。数组也就变成了 $f[i][j][1]$，和 $f[i][j][0]$，分别表示从左边来还是从右边来。如果一直从左转移，那么需要加上上边的害怕值，从上同理.
那么我们这样就得到了状态转移方程和预处理。预处理val[i][j]数组表示第i行j列会得到的害怕值，根据上边的分析得到只需要看这个点右边和下边即可。

 $f_{i,j,0/1}$ i，j是位置，0指左，1指右

初始化

for(int i=0;i<=n;i++)
	for(int j=0;j<=m;j++)
		v[i][j]+=a[i][j+1]+a[i+1][j];//记录当前点右边和下边的1的个数
memset(f,0x3f,sizeof(f));
f[1][0][0]=f[1][0][1]=v[1][0]; 
f[0][1][0]=f[0][1][1]=v[0][1];
f[1][1][0]=f[1][1][1]=0;

状态转移

  • 从左边来：f[i][j][0]=min(f[i][j-1][0]+v[i][j]+a[i-1][j],f[i][j-1][1]+v[i][j]);

  • 从右边来：f[i][j][1]=min(f[i-1][j][1]+v[i][j]+a[i][j-1],f[i-1][j][0]+v[i][j]);

总代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,v[1010][1010],f[1010][1010][2];
int a[1010][1010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			v[i][j]+=a[i][j+1]+a[i+1][j];
	memset(f,0x3f,sizeof(f));
	f[1][0][0]=f[1][0][1]=v[1][0]; 
	f[0][1][0]=f[0][1][1]=v[0][1];
	f[1][1][0]=f[1][1][1]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			f[i][j][0]=min(f[i][j-1][0]+v[i][j]+a[i-1][j],f[i][j-1][1]+v[i][j]);
			f[i][j][1]=min(f[i-1][j][1]+v[i][j]+a[i][j-1],f[i-1][j][0]+v[i][j]);
			//cout<<f[i][j][0]<<' '<<f[i][j][1]<<" * ";
		}
		//cout<<endl;
	}
	cout<<min(f[n][m][0],f[n][m][1]);
	return 0;
}