DP【洛谷P2295】 MICE

P2295 MICE

S国的动物园是一个N*M的网格图，左上角的坐标是(1,1)，右下角的坐标是(N,M)。

小象在动物园的左上角，它想回到右下角的家里去睡觉，但是动物园中有一些老鼠，而小象又很害怕老鼠。动物园里的老鼠是彼此互不相同的。小象的害怕值定义为他回家的路径上可以看见的不同的老鼠的数量。若小象当前的位置为(x1,y1)，小象可以看见老鼠，当且仅当老鼠的位置(x2,y2)满足|x1-x2|+|y1-y2|<=1。由于小象很困了，所以小象只会走一条最近的路回家，即小象只会向下或者向右走。现在你需要帮小象确定一条回家的路线，使得小象的害怕值最小。

画画图，分四种情况转移，开三维。

f(i)(j)(1)表示(i,j)这个点由(i-1,j)转移过来的最小答案。

f(i)(j)(2)表示(i,j)这个点由(i,j-1)转移过来的最小答案。

模拟一下就过了喵喵喵。。。

code：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int wx=1017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int a[wx][wx];

int f[wx][wx][3];

int n,m;

int dx[]={0,1,0,-1,0};

int dy[]={0,0,1,0,-1};

int main(){

	n=read(); m=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			a[i][j]=read();

	memset(f,0x3f,sizeof f); f[1][1][1]=f[1][1][2]=a[1][1]+a[2][1]+a[1][2];

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(i==1&&j==1)continue;

			f[i][j][1]=min(f[i-1][j][1]+a[i+1][j]+a[i][j-1]+a[i][j+1],

				f[i-1][j][2]+a[i+1][j]+a[i][j+1]);

			f[i][j][2]=min(f[i][j-1][2]+a[i][j+1]+a[i-1][j]+a[i+1][j],

				f[i][j-1][1]+a[i][j+1]+a[i+1][j]);

		}

	}

	printf("%d\n",min(f[n][m][1],f[n][m][2]));

	return 0;

}