搜索小练#9后续

Posted on Edited on In

给出完整的AC代码 这个题只需要写一个队列....

枚举两个人可能选的坐标情况，作为不同的初始状态

对每个初始状态进行bfs搜索，得到木板上的每块草地被烧完的时间

其中烧完杯子耗时最久的时间就是总时间

然后根据此初始状态的耗时去更新答案

得到所有初始状态中耗时最小的时间

若无法更新得到，则输出-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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 66, INF = 214748364;

int T, n, m, k, res;
int a[N][N], v[N][N], cost[N][N];

int dx[N] = {0, 0, 1, -1};
int dy[N] = {1, -1, 0, 0};

struct node {int x, y;node (int x, int y):x(x),y(y){}};

inline void getsum () {
    int tmp = -1;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            if (a[i][j] && !v[i][j]) return;
            if (a[i][j] && cost[i][j] > tmp)
                tmp = cost[i][j];
        }
    if (tmp < res) res = tmp;
}

inline void bfs (int nx, int ny, int s, int t) {
    memset (v, 0, sizeof v);
    memset (cost, -1, sizeof cost);
    queue<node>q;
    v[nx][ny] = 1, cost[nx][ny] = 0;
    q.push(node(nx, ny));
    if (!v[s][t]) {
        v[s][t] = 1;
        cost[s][t] = 0;
        q.push(node(s, t));
    }
    while (q.size()) {
        node tmp = q.front(); q.pop();
        for (int i = 0; i < 4; ++ i) {
            int curx = tmp.x+dx[i], cury = tmp.y+dy[i];
            if ((curx < 1) || (curx > n) || (cury < 1) || (cury > m)) continue;
            if (!v[curx][cury] && a[curx][cury]) {
                v[curx][cury] = 1;
                cost[curx][cury] = cost[tmp.x][tmp.y]+1;
                q.push(node(curx, cury));
            }
        }
    }
    getsum();
}

int main () {
    char ch[N];
    scanf ("%d", &T);
    while (T --> 0) {
        ++ k; res = INF;
        scanf ("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            scanf ("%s", ch+1);
            for (int j = 1; j <= m; ++ j)
                a[i][j] = (ch[j] == '#') ? 1 : 0;
        }
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j)
                for (int ni = 1; ni <= n; ++ ni)
                    for (int nj = 1; nj <= m; ++ nj)
                        if (a[i][j] && a[ni][nj])
                            bfs (i, j, ni, nj);
        if (res != INF) printf ("Case %d: %d\n", k, res);
        else printf ("Case %d: -1\n", k);
    }
    return 0;
}

体会二维坐标的写法以及结构体的定义函数

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
/*
 * By Youngore
 * Time:20.10.17
 * */
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#define INF 214748364
using namespace std;
const int N = 16;

int n, m, t, T, res;
int a[N][N], vis[N][N], dis[N][N];
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

struct yhy
{
    int x, y;
    yhy(int x, int y):x(x), y(y){}
};

inline void yhy_clear()
{
    memset(vis, 0, sizeof vis);
    memset(dis, -1, sizeof dis);
}

inline void get_sum()
{
    int i, j, tmp = -1;
    for (i = 1; i <= n; ++ i)
    {
        for (j = 1; j <= m; ++ j)
        {
            if ((a[i][j] && ! vis[i][j])) return;
            if (a[i][j] && dis[i][j] > tmp) tmp = dis[i][j];
        }
    }
    return (void)(res = (res > tmp) ? tmp : res);
}

inline void bfs(int x, int y, int nx, int ny)
{
    yhy_clear(); queue<yhy>q;
    vis[x][y] = 1, dis[x][y] = 0, q.push(yhy(x, y));
    if (! vis[nx][ny])
    {
        vis[nx][ny] = 1, dis[nx][ny] = 0;
        q.push(yhy(nx, ny));
    }
    while (! q.empty())
    {
        yhy tmp = q.front(); q.pop();
        for (int i = 0; i < 4; ++ i)
        {
            int curx = tmp.x + d[i][0], cury = tmp.y + d[i][1];
            if (curx < 1 || curx > n || cury < 1 || cury > m) continue;
            if (! vis[curx][cury] && a[curx][cury])
            {
                vis[curx][cury] = 1;
                dis[curx][cury] = dis[tmp.x][tmp.y] + 1;
                q.push(yhy(curx, cury));
            }
        }
    }
    return (void)(get_sum());
}

inline int youngore()
{
    scanf ("%d", &T);
    while (T --> 0)
    {
        ++ t; res = INF;
        int i, j, ni, nj; scanf ("%d%d", &n, &m);
        for (i = 1; i <= n; ++ i)
        {
            char ch[N];
            scanf ("%s", ch + 1);
            for (j = 1; j <= m; ++ j) a[i][j] = (ch[j] == '#') ? 1 : 0;
        }
        for (i = 1; i <= n; ++ i) for (j = 1; j <= m; ++ j)
        for (ni = 1; ni <= n; ++ ni) for (nj = 1; nj <= m; ++ nj)
            if (a[i][j] && a[ni][nj]) bfs(i, j, ni, nj);
        if (res != INF) printf ("Case %d: %d\n", t, res);
        else printf ("Case %d: -1\n", t);
    }
    return 0;
}

int search_ex = youngore();

signed main() {;}