MYF

HDU 5335 Walk Out

Posted on | In | | Visitors

题目链接

HDU 5335
BFS

题目分析

题目大意

给一个n*m的地图，每一个位置有一个数字0或者1，问，从(1, 1)到(n, m)，记录每一次踩的格子，形成一个二进制字符串，问这个字符串所表示的最小的数字。

解析

先BFS找到距离终点(n, m)最近的曼哈顿距离的且值为0的点，然后从这个点的下一位开始找，找到(n, m)所形成的路径。

参考链接：http://blog.csdn.net/caduca/article/details/47154213

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//参考链接：http://blog.csdn.net/caduca/article/details/47154213

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int t,n,m;
char mp[1005][1005];
int vis[1005][1005];
int mx[]={0,0,1,-1};
int my[]={-1,1,0,0};
struct node{
    int x,y;
    node(int _x=1,int _y=1):x(_x),y(_y){}
};
bool inmap(int xx,int yy){
    return xx>=1&&xx<=n&&yy>=1&&yy<=m;
}
int bfs(){
    Memset(vis, 0);
    if (mp[1][1]!='0') {
        //没有前导零的情况
        return 1;
    }
    int rt=0;   //记录离(1, 1)最远的'0'的曼哈顿距离
    queue<node>q;
    q.push(node(1,1));
    vis[1][1]=1;
    while (!q.empty()) {
        node tmp=q.front();
        q.pop();
        for (int i=0; i<4; i++) {
            int xx=tmp.x+mx[i];
            int yy=tmp.y+my[i];
            if (inmap(xx,yy)&&!vis[xx][yy]&&mp[xx][yy]=='0') {
                vis[xx][yy]=1;
                q.push(node(xx,yy));
            }
        }
        rt=max(rt, tmp.x+tmp.y);
    }
    return rt;
}
int main(){
    scanf("%d",&t);
    while (t--) {
        scanf("%d %d",&n,&m);
        for (int i=1; i<=n; i++) {
            scanf("%s",mp[i]+1);
        }
        int st=bfs();//找到最后离(n, m)最近的'0'的点到(0, 0)的曼哈顿距离
        if (st==m+n) {
            //可以找到一条从(1, 1)到(n, m)全为'0'的通路
            puts("0");
            continue;
        }
        
        vector<node> v[2005];
        int cur=st;//记录前一位0出现的位置
        for (int xx=1; xx<=n; xx++) {
            int yy=st-xx;
            if (inmap(xx,yy)&&vis[xx][yy]) {
                v[st].push_back(node(xx,yy));
            }
        }
    
        for (int i=st+1; i<=n+m; i++) {
            if (cur==1) {
                for (int xx=1; xx<=n; xx++) {
                    int yy=i-xx;
                    if (inmap(xx,yy)&&mp[xx][yy]=='0') {
                        cur=i;
                        v[i].push_back(node(xx,yy));
                    }
                }
            }
            else{
                for (int xx=1; xx<=n; xx++) {
                    int yy=i-xx;
                    if (inmap(xx,yy)&&mp[xx][yy]=='0') {
                        for (int j=0; j<v[cur].size(); j++) {
                            node now=v[cur][j];
                            if (now.x<=xx&&now.y<=yy) {
                                v[i].push_back(node(xx,yy));
                                break;
                            }
                        }
                    }
                }
                if (v[i].size()>0) {
                    cur=i;
                }
            }
        }
        for (int i=st+1; i<=n+m; i++) {
            if (v[i].size()>0)
                printf("0");
            else
                printf("1");
        }
        puts("");
    }
}