题号：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; } |