CodeChef Little Elephant and Mouses [DP]

https://www.codechef.com/problems/LEMOUSE

---

题意：

有一个n *m的网格。有一头大象，初始时在(1,1)，要移动到(n,m)，每
次只能向右或者向下走。有些格子中有老鼠，如果大象所在的格子和某个有老
鼠的格子的曼哈顿距离$\e$1，大象就会被那只老鼠吓到。
求一条移动路径，使得吓到过大象的老鼠数量最少。n;m $\le$100。

---

开始刷济南集训hzc的课件啦！

最简单的一道$DP$

一只老鼠只会吓大象一次$f[i][j][0/1]$记录从左还是上走来的，转移时讨论一下就行了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=,INF=1e9+;

double eps=1e-;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int m,n,a[N][N],s[N][N];

char str[N];

int f[N][N][];

void dp(){

    f[][][]=f[][][]=s[][];

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++){

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

            if(j-!=){

                int t1=INF,t2=INF;

                if(j-!=||i==)

                    t1=f[i][j-][];

                if(i-!=)

                    t2=f[i][j-][]-a[i-][j];

                f[i][j][]=min(t1,t2)+s[i][j]-a[i][j-]-a[i][j];

            }

            if(i-!=){

                int t1=INF,t2=INF;

                if(i-!=||j==)

                    t1=f[i-][j][];

                if(j-!=)

                    t2=f[i-][j][]-a[i][j-];

                f[i][j][]=min(t1,t2)+s[i][j]-a[i-][j]-a[i][j];

            }

        }

    //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("f %d %d  %d %d\n",i,j,f[i][j][0],f[i][j][1]);

        //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("%d%c",f[i][j][0],j==n?'\n':' ');puts("");

        //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("%d%c",f[i][j][1],j==n?'\n':' ');puts("");

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

}

int main(){

    freopen("in","r",stdin);

    int T=read();

    while(T--){

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

        memset(s,,sizeof(s));

        for(int i=;i<=m;i++){

            scanf("%s",str+);

            for(int j=;j<=n;j++){

                a[i][j]=str[j]-'';

                if(a[i][j])    s[i][j]++,s[i-][j]++,s[i+][j]++,s[i][j-]++,s[i][j+]++;

            }

        }

        //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("%d%c",a[i][j],j==n?'\n':' ');puts("");

        //for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) printf("%d%c",s[i][j],j==n?'\n':' ');puts("");

        dp();

    }

}