#include<bits/stdc++.h> using namespace std; const int N = 3000 + 5; int n, m; int dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, -1, 1}; bool Map[N][N], vis[N][N], in[N][N]; int maxx, maxtmp; struct Node{ int x, y; }; inline int add (int x, int y) { memset (in, 0, sizeof (in)); int res = 0; queue< Node >q; q.push((Node){x, y}); in[x][y] = 1; while (q.size ()) { Node now = q.front (); q.pop (); for (int i = 1; i <= 4; i++) { int a = now.x + dx[i], b = now.y + dy[i]; if (Map[a][b] == 0 || a < 1 || b < 1 || a > n || b > m) res ++; if (a < 1 || b < 1 || a > n || b > m || in[a][b] || Map[a][b] == 0) continue; in[a][b] = 1; q.push((Node){a, b}); } } return res; } inline void bfs (int x, int y) { int stp = 0; queue< Node >q; q.push((Node){x, y}); vis[x][y] = 1; while (q.size ()) { Node now = q.front (); q.pop (); stp++; for (int i = 1; i <= 4; i++) { int a = now.x + dx[i], b = now.y + dy[i]; if (a < 1 || b < 1 || a > n || b > m || vis[a][b] || Map[a][b] == 0) continue; vis[a][b] = 1; q.push((Node){a, b}); } } if (stp >= maxx) { int tmp = add(x, y); // cout<<tmp<<endl; if (maxx == 0) maxx = stp, maxtmp = tmp; else if (stp > maxx) maxx = stp, maxtmp = tmp; else if (tmp < maxtmp) maxtmp = tmp; } } signed main () { char ch; ios::sync_with_stdio(false); cin>>n>>m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin>>ch, Map[i][j] = ch - '0'; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) if (vis[i][j] == 0 && Map[i][j] == 1) bfs(i, j); } // printf ("%d\n", maxx); if (maxx == 0 ) printf ("What a pity!\n"); else printf ("%d\n", maxtmp); return 0; }
核心思想:找bfs找连通块,与最大的进行比较,并且计算外围周长,更新答案
不知道有什么问题,谜之WA
全部评论
(3) 回帖