HDU 5335 Walk Out(2015多校联合)

发表于   |  

题目链接

戳我

题目大意

$m * n$的矩阵，每个格子是0或者1，探险家初始位置是$(1, 1)$，终点位置是$(n, m)$,且只能向 上下左右四个方向走,因为从 起点到终点 所走的路径是由01构成的,故可表示成二进制数,要求寻找一条路径表示的二进制数最小.

样例解释

2 //T 两组测试样例
2 2 // n,m, 行 列
11 //第一行
11 //第二行 路径为$(1,1)->(1,2)->(2,2)$(也可以是其他),故为111
3 3 //n, m
001
111
101 //路径为$(1,1)->(1,2)->(2,2)->(3->2)->(3,3)$故为00101,即101

解题思路

因为是二进制,所以要尽可能的走0,走0走的离终点越近越好.

  • 第一步: 一直走0,走到不能走0为止,从这些0中挑出来所有距离终点 曼哈顿距离最小的
  • 第二步: 从第一步挑出来的 0 为起点 搜索,且只搜右和下两个方向遍历每一层,如果该层有 0 必然选择 0,并把 0 加入队列,如果该层只有 1 ,则把所有的 1 都加入队列,依次遍历下一层.

代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+10;
int MOVE[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
struct Point
{
    int x, y;
    int step;
}p[maxn];
int vis[maxn][maxn];
char g[maxn][maxn];
int n, m;
char ans[maxn*4];
queue<Point> q;
queue<Point> q1;

inline bool judge(int x, int y)
{
    if(x < 0 || x >= n || y < 0 || y >= m) return false;
    return true;
}

void BFS(int x, int y)
{
    while(!q.empty()) q.pop();
    int xx, yy;
    int dis = m+n-2;
    Point s, now, next;
    s.x = x; s.y = x; s.step = 0;
    q.push(s);

    while(!q.empty() && g[x][y] == '0') //开始一直走0
    {
        now = q.front(); q.pop();
        q1.push(now);
        if(n-1-now.x+m-1-now.y < dis) //寻找离终点最近的 0 点 的距离
        {
            dis = n-1-now.x+m-1-now.y;
        }
        for(int i = 0; i < 4; i++)
        {
            xx = now.x + MOVE[i][0];
            yy = now.y + MOVE[i][1];
            if(!judge(xx, yy)) continue;
            if(g[xx][yy] == '1') continue;
            if(vis[xx][yy]) continue;
            vis[xx][yy] = 1;
            next.x = xx; next.y = yy;
            next.step = now.step + 1;
            q.push(next);
        }
    }//q已空

    while(!q1.empty())
    {
        now = q1.front(); q1.pop();
        if(n-1-now.x+m-1-now.y == dis) //把到终点的距离等于dis的0点加入队列
        {
            q.push(now);
        }
    } //q1 已空
    if(dis == 0) //此时说明可以直接走0到终点
    {
        ans[0] = '0';
        ans[1] = '\0';
        return;
    }

    int t = 0; // 所走的路径
    char flag = '1';
    if(dis == n+m-2) ans[t++] = '1';
    while(!q.empty())
    {
        flag = '1';
        while(!q.empty()) //属于同一层的都找出来
        {
            now = q.front(); q.pop();
            //printf("x = %d, y = %d, step = %d\n", now.x, now.y, now.step);
            for(int i = 0; i < 2; i++)
            {
                xx = now.x + MOVE[i][0];
                yy = now.y + MOVE[i][1];
                if(!judge(xx, yy) || vis[xx][yy]) continue;
                vis[xx][yy] = 1;
                if(g[xx][yy] == '0') flag = '0'; //如果该层有0,则把0都挑出来作为下一步
                next.x = xx; next.y = yy; next.step = now.step + 1;
                q1.push(next);
            }
        }
        while(!q1.empty())
        {
            now = q1.front(); q1.pop();
            if(now.x == n-1 && now.y == m-1)
            {
                ans[t++] = g[n-1][m-1];
                ans[t] = '\0';
                return;
            }
            if(g[now.x][now.y] == flag)//如果该层有0,则把0都挑出来作为下一步
            {
                q.push(now);
            }
        }
        ans[t++] = flag;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        clc(vis, 0);
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
        {
            scanf("%s", g[i]);
        }
        if(n == 1 && m == 1)
        {
            puts(g[0]);
            continue;
        }
        BFS(0, 0);
        printf("%s\n", ans);
    }
    return 0;
}