HDU 5335 Walk Out（多校）

Walk Out

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2912    Accepted Submission(s): 599


Problem Description

In an n∗m maze, the right-bottom corner is the exit (position (n,m) is the exit). In every position of this maze, there is either a 0 or a 1 written on it.

An explorer gets lost in this grid. His position now is (1,1), and he wants to go to the exit. Since to arrive at the exit is easy for him, he wants to do something more difficult. At first, he'll write down the number on position (1,1). Every time, he could make a move to one adjacent position (two positions are adjacent if and only if they share an edge). While walking, he will write down the number on the position he's on to the end of his number. When finished, he will get a binary number. Please determine the minimum value of this number in binary system.

 


Input

The first line of the input is a single integer T (T=10), indicating the number of testcases.

For each testcase, the first line contains two integers n and m (1≤n,m≤1000). The i-th line of the next n lines contains one 01 string of length m, which represents i-th row of the maze.

 


Output

For each testcase, print the answer in binary system. Please eliminate all the preceding 0 unless the answer itself is 0 (in this case, print 0 instead).

 


Sample Input

2 2 2 11 11 3 3 001 111 101

 


Sample Output

111 101

 


Author

XJZX

 


Source

2015 Multi-University Training Contest 4

 


Recommend

wange2014   |   We have carefully selected several similar problems for you:  5342 5341 5340 5339 5338

本题思路：

1.先判断第一个点是不是0，如果是0先把所有的0都走一遍，找到哈曼顿距离最小的点（可能会有几个）。

这个过程可以用DFS也可以BFS（建议BFS,因为DFS会爆栈，必须自己把栈开导最大，后面会说明）

2.如果第一点不是0，直接从第一个点开始搜，只搜下和右两个方向，如果这两个方向有两个0，输出0，把两个0都加入队列；如果只有一个0，输出0，只把0那个点加入队列；如果是两个1，也把两个点都加入队列。

3.如果第一个点是0，再把这个0的右边的点和下边的点（超边界的不算）都加入队列开始用2的方法搜。

开始用DFS搜

  1 #pragma comment(linker, "/STACK:10240000000000,10240000000000")//这行代码不加就会STACK_OVERFLOW
  2 #include<queue>
  3 #include<math.h>
  4 #include<stdio.h>
  5 #include<string.h>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 #define N 1234
 10 struct point
 11 {
 12     int x,y,d;
 13 }st[N*2];
 14 
 15 int dx[]={1,0,-1,0};
 16 int dy[]={0,1,0,-1};
 17 int n,m,k,dis,flag;
 18 char mat[N][N];
 19 bool vis[N][N];
 20 
 21 void dfs(int x,int y)
 22 {
 23     if(x<1||x>n||y<1||y>m)return;
 24     if(mat[x][y]=='1')return;
 25     if(vis[x][y]==1)return;
 26     vis[x][y]=1;
 27     if(dis<x+y)
 28     {
 29         k=0;
 30         dis=x+y;
 31         st[k].x=x;
 32         st[k++].y=y;
 33     }
 34     else if(dis==x+y)
 35     {
 36         st[k].x=x;
 37         st[k++].y=y;
 38     }
 39     for(int i=0;i<4;i++)
 40         dfs(x+dx[i],y+dy[i]);
 41 }
 42 void bfs()
 43 {
 44     memset(vis,0,sizeof(vis));
 45     queue<point>q1;
 46     queue<point>q2;
 47     for(int i=0;i<k;i++)
 48     {
 49         if(mat[st[i].x][st[i].y]=='0')
 50         {
 51             if(st[i].x==n&&st[i].y==m){printf("0");return;}
 52             point a1=st[i],a2=st[i];
 53             a1.x++;a2.y++;
 54             if(a1.x<=n)
 55                 q1.push(a1),vis[a1.x][a1.y]=1;
 56             if(a2.y<=m)
 57                 q1.push(a2),vis[a2.x][a2.y]=1;
 58         }
 59         else
 60             q1.push(st[i]),vis[st[i].x][st[i].y]=1;
 61     }
 62     printf("1");
 63     if(vis[n][m])return;
 64     while(1)
 65     {
 66         flag=1;
 67         while(!q1.empty())
 68         {
 69             point cur=q1.front();
 70             q1.pop();
 71             for(int i=0;i<2;i++)
 72             {
 73                 point next=cur;
 74                 next.x+=dx[i],next.y+=dy[i];
 75                 if(vis[next.x][next.y] || next.x<1 || next.x>n || next.y<1 || next.y>m)continue;
 76                 if(mat[next.x][next.y] == '0')
 77                     flag = 0;
 78                 q2.push(next);
 79                 vis[next.x][next.y]=1;
 80             }
 81         }
 82         printf("%d",flag);
 83         if(vis[n][m])return;
 84 
 85         while(!q2.empty())
 86         {
 87             point cur=q2.front();
 88             q2.pop();
 89             if(flag==1)
 90                 q1.push(cur);
 91             else if(flag==0 && mat[cur.x][cur.y]=='0')
 92                 q1.push(cur);
 93         }
 94     }
 95 }
 96 
 97 int main()
 98 {
 99     int t;cin>>t;
100     while(t--)
101     {
102         memset(vis,0,sizeof(vis));
103         dis=0;
104         scanf("%d%d",&n,&m);
105         for(int i=1;i<=n;i++)
106             scanf("%s",mat[i]+1);
107 
108         if(mat[1][1]=='1')
109             st[0].x=1,st[0].y=1,k=1;
110         else
111             dfs(1,1);
112         bfs();
113         cout<<endl;
114     }
115     return 0;
116 }
117 
118 //几组比较好的数据
119 
120 /*
121 5
122 2 2
123 01
124 11
125 2 2
126 00
127 11
128 2 2
129 00
130 00
131 3 3
132 000
133 110
134 110
135 3 3
136 000
137 110
138 111
139 
140 
141 */

开始用BFS搜（推荐）

  1 #include<queue>
  2 #include<math.h>
  3 #include<stdio.h>
  4 #include<string.h>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 #define N 1234
  9 struct point
 10 {
 11     int x,y;
 12 }st[N*2];
 13 int dx[]={1,0,-1,0};
 14 int dy[]={0,1,0,-1};
 15 int n,m,k,dis;
 16 char mat[N][N];
 17 bool vis[N][N];
 18 
 19 void bfs1()
 20 {
 21     memset(vis,0,sizeof(vis));
 22     queue<point>q;
 23     point first;
 24     first.x=first.y=1;
 25     q.push(first);vis[1][1]=1;
 26     st[0].x=st[0].y=1;
 27     k=1;
 28     while(!q.empty())
 29     {
 30         point cur=q.front();
 31         q.pop();
 32         for(int i=0;i<4;i++)
 33         {
 34             point next=cur;
 35             next.x+=dx[i],next.y+=dy[i];
 36             if(next.x<1||next.x>n||next.y<1||next.y>m)continue;
 37             if(vis[next.x][next.y] || mat[next.x][next.y]=='1')continue;
 38             q.push(next);vis[next.x][next.y]=1;
 39             if(dis<next.x+next.y)
 40             {
 41                 k=0;
 42                 dis=next.x+next.y;
 43                 st[k].x=next.x;
 44                 st[k++].y=next.y;
 45             }
 46             else if(dis==next.x+next.y)
 47             {
 48                 st[k].x=next.x;
 49                 st[k++].y=next.y;
 50             }
 51         }
 52     }
 53 }
 54 void bfs()
 55 {
 56     memset(vis,0,sizeof(vis));
 57     queue<point>q1;
 58     queue<point>q2;
 59     for(int i=0;i<k;i++)
 60     {
 61         if(mat[st[i].x][st[i].y]=='0')
 62         {
 63             if(st[i].x==n&&st[i].y==m){printf("0");return;}
 64             point a1=st[i],a2=st[i];
 65             a1.x++;a2.y++;
 66             if(a1.x<=n)
 67                 q1.push(a1),vis[a1.x][a1.y]=1;
 68             if(a2.y<=m)
 69                 q1.push(a2),vis[a2.x][a2.y]=1;
 70         }
 71         else
 72             q1.push(st[i]),vis[st[i].x][st[i].y]=1;
 73     }
 74     printf("1");
 75     if(vis[n][m])return;
 76     while(1)
 77     {
 78         int flag=1;
 79         while(!q1.empty())
 80         {
 81             point cur=q1.front();
 82             q1.pop();
 83             for(int i=0;i<2;i++)
 84             {
 85                 point next=cur;
 86                 next.x+=dx[i],next.y+=dy[i];
 87                 if(vis[next.x][next.y] || next.x<1 || next.x>n || next.y<1 || next.y>m)continue;
 88                 if(mat[next.x][next.y] == '0')
 89                     flag = 0;
 90                 q2.push(next);
 91                 vis[next.x][next.y]=1;
 92             }
 93         }
 94         printf("%d",flag);
 95         if(vis[n][m])return;
 96 
 97         while(!q2.empty())
 98         {
 99             point cur=q2.front();
100             q2.pop();
101             if(flag==1)
102                 q1.push(cur);
103             else if(flag==0 && mat[cur.x][cur.y]=='0')
104                 q1.push(cur);
105         }
106     }
107 }
108 
109 int main()
110 {
111     int t;cin>>t;
112     while(t--)
113     {
114         dis=0;
115         scanf("%d%d",&n,&m);
116         for(int i=1;i<=n;i++)
117             scanf("%s",mat[i]+1);
118 
119         if(mat[1][1]=='1')
120             st[0].x=1,st[0].y=1,k=1;
121         else
122             bfs1();
123         bfs();
124         cout<<endl;
125     }
126     return 0;
127 }

其他：

1输图的时候不要%c输入，用%s输入，速度会快很多，这题如果用%c输入会TLE,(花了一下午时间找为什么TLE，最后发现居然是因为输图方式。） 所以以后都要用：

for(int i=0;i<n;i++)
    scanf("%s",mat[i];
or
for(int i=1;i<=n;i++)
    scanf("%s",mat[i]+1);

2 dfs是很容易爆栈的，这题就是我开始写的用dfs的就爆栈了，这时候有一个处理办法：在代码最前面加：#pragma comment(linker, "/STACK:10240000000000,10240000000000") 这句意思是自己开一个非常大的栈，STACK:后面那数字好像已经是能开的最大的了。
此题中加入这一行本来的Runtime Error（STACK_OVERFLOW)就会变成 Accepted！

但是好像正规比赛不允许使用这种方式。

　　　　　　

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wmxl/p/4699826.html