洛谷 穿越栅栏 Overfencing

题号:1519

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<list>
#include<functional>
#include<string>
using namespace std;
int w, h, m=0;
char graph[300][300];
bool visited[300][300];
int steps[300][300];
int check_x[5] = {0,1,-1,0,0},
check_y[5] = {0,0,0,1,-1},
step_x[5] = {0,2,-2,0,0},
step_y[5] = {0,0,0,2,-2};
struct node {
    int x, y, step;
    node(int x1,int y1,int step1) {
        x = x1; y = y1; step = step1;
    }
};
bool check(int cx, int cy, int sx, int sy) {
    if (!visited[sx][sy] && graph[cx][cy] == ' '&&sx % 2 == 0 && sy % 2 == 0 && sx < 2 * h + 1 && sx>1 && sy < 2 * w + 1 && sy>1)return true;
    return false;
}
void BFS(int x,int y) {
    int maxstep = 0;
    queue<node> q;
    memset(visited, false, sizeof(visited));
    q.push(node(x, y, 0));
    while (!q.empty()) {
        node t = q.front(); q.pop();
        if (steps[t.x][t.y]> t.step)steps[t.x][t.y] = t.step;
        if (visited[t.x][t.y])continue;
        visited[t.x][t.y] = true;
        for (int i = 1; i <= 4; i++) {
            if (check(t.x + check_x[i], t.y + check_y[i], t.x + step_x[i], t.y + step_y[i]))q.push(node(t.x + step_x[i], t.y + step_y[i], t.step + 1));
        }
    }
}
int main() {
    cin >> w >> h;
    cin.getline(graph[0] + 1, 280);
    memset(steps, 0x7f, sizeof(steps));
    for (int i = 1; i <= 2 * h + 1; i++) {
        cin.getline(graph[i] + 1, 280);
    }
    for (int i = 2; i <= 2 * w; i++) {
        if (graph[1][i] == ' ')BFS(2, i);
        if (graph[2 * h + 1][i] == ' ')BFS(2 * h, i);
    }
    for (int i = 2; i <= 2 * h; i++) {
        if (graph[i][1] == ' ')BFS(i, 2);
        if (graph[i][2 * w + 1] == ' ')BFS(i, 2 * w);
    }
    for (int i = 2; i <= 2 * h; i+=2) {
        for (int j = 2; j <= 2 * w; j += 2) {
            if (steps[i][j] > m&&steps[i][j]!=0x7f7f7f7f)m = steps[i][j];
        }
    }
    cout << m+1 << endl;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注