2015 Multi-University Training Contest 4

1009 Walk Out

状态压缩方面，虽然想到了用一维的x+y替代二维的x,y，但并没有做到位。
既然可以转化成二维DP，还有何搜索必要
寻找合适的出发点时，不要陷入“极近点”而丢失了“最近点”！

#include<cctype>

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int inf=0x7fffffff;
const double eps=1e-3;

typedef pair<int,int> pr;
const int dir[4][2]={ {0,-1},{0,1},{-1,0},{1,0}};
const int maxn=1010;
const int maxm=1010;
int n,m,X0,Y0;
bool g[maxn][maxm],f[maxn][maxm],vis[maxn][maxm];
char str[maxn];

bool can(int x,int y){
    if (x<1||x>n||y<1||y>m) return 0;
    return 1;
}
bool can(pr p){
    return can(p.first,p.second);
}
int mdis(int x,int y){
    return abs(x-n)+abs(y-m);
}
int mdis(pr p){
    return mdis(p.first,p.second);
}
int geth(pr p){
    return p.first+p.second;
}

void find0(int x,int y){
        if (vis[x][y]||!can(x,y)) return;
        vis[x][y]=1;
        if (g[x][y]) return;
        f[x][y]=1;
        if (x+y>X0+Y0)
        {
            X0=x;Y0=y;
        }
        for(int i=0;i<4;i++) find0(x+dir[i][0],y+dir[i][1]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for(int j=1;j<=m;j++)
            {
                if (str[j]=='1') g[i][j]=1;
                else g[i][j]=0;
            }
        }

        X0=0;Y0=0;
        memset(vis[0],0,maxn*maxm*sizeof(vis[0][0]));
        memset(f[0],0,maxn*maxm*sizeof(f[0][0]));
        find0(1,1);
        //cout<<X0<<' '<<Y0<<endl;
        if (X0+Y0==n+m){
            printf("%d\n",0);
            continue;
        }
        if (X0+Y0<2)
        {
            X0=1;Y0=1;
            f[1][1]=1;
            printf("1");
        }
        for(int i=X0+Y0;i<n+m;i++)
        {
            int k=1;
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                k=min(k,min(k1,k2));
            }
            for(int j=max(1,i-m);j<=min(n,i-1);j++)
                if (f[j][i-j])
            {
                int k1=j<n?g[j+1][i-j]:1;
                int k2=i-j<m?g[j][i-j+1]:1;
                if (k1==k) f[j+1][i-j]=1;
                if (k2==k) f[j][i-j+1]=1;
            }
            printf("%d",k);
        }
        puts("");
    }
    return 0;
}