搜索小练#9

Posted on Edited on In

题目

今天没写完

晚上倒是有一段时间

不过我去弄Atom了......

明天计划:

切掉这个题 把以前做过的搜索题复习一下

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 	66, INF = 214748364;

int T, n, m, res = INF;
int a[N][N], flag;
char s[N];

int dx[3] = {0, 0, 1, -1};
int dy[3] = {1, -1, 0, 0};
int vs[N][N], vt[N][N];
int sdis[N][N], tdis[N][N];

struct node {int x, y;};

inline int bfs (int curx, int cury, int curs, int curt) {
    // if (x == nx && y == ny) calc();
    queue<node>qs; queue<node>qt;
  node l, r;
    l.x = curx, l.y = cury, r.x = curs, r.y = curt;
    qs.push(l); qt.push(r);
    memset (vs, 0, sizeof vs), memset (vt, 0, sizeof vt);
    memset (sdis, 0, sizeof sdis), memset (tdis, 0, sizeof tdis);
    int ans(0);
    while (qs.size()) {
        node tmp = qs.front(); qs.pop();
        for (int i = 0; i < 3; ++ i) {
            node nows;
            nows.x = tmp.x+dx[i], nows.y = tmp.y+dy[i];
            if ((nows.x > n)||(nows.x < 1)||(nows.y > m)||(nows.y < 1)) continue;
            if (!vs[nows.x][nows.y] && a[nows.x][nows.y]){
                vs[nows.x][nows.y] = 1;
                qs.push(nows);
                sdis[nows.x][nows.y] = sdis[tmp.x][tmp.y]+1;

            }
        }
    }
    while (qt.size()) {
        node tmp = qt.front(); qt.pop();
        for (int i = 0; i < 3; ++ i) {
            node nows;
            nows.x = tmp.x+dx[i], nows.y = tmp.y+dy[i];
            if ((nows.x > n)||(nows.x < 1)||(nows.y > m)||(nows.y < 1)) continue;
            if (!vt[nows.x][nows.y] && a[nows.x][nows.y]){
                vt[nows.x][nows.y] = 1;
                qt.push(nows);
                tdis[nows.x][nows.y] = tdis[tmp.x][tmp.y]+1;
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            if ((!vs[i][j] || !vt[i][j]) && a[i][j]) {
                flag = true;
                return;
            }
        }
}

int main () {
    scanf ("%d", &T);
    while (T --> 0) {
        flag = false, res = 0;
        scanf ("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%s", s+1);
            for (int j = 1; j <= m; ++ j)
                a[i][j] = (s[j] == '#') ? 1 : 0;
        }
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                if (a[i][j])
        for (int ni = 1; ni <= n; ++ ni)
            for (int nj = 1; nj <= m; ++ nj)
                if (a[ni][nj])
                    bfs (i, j, ni, nj);
        if (flag) cout << "-1" << '\n';
        else cout << res << '\n';
    }
    return 0;
}