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;
}
05-27 05:46