1 条题解
-
0
`
//#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; int n,m; bool vis[1005][1005]; char a[1005][1005]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; struct node{ int x; int y; }; struct node1{ int x; int y; }s[1000005]; int ans[1002][1002]; void dfs(int x,int y) { queue<node>op; node p; p.x = x,p.y = y; op.push(p); int cnt = 0; while(!op.empty()){ p = op.front(); op.pop(); for(int i = 0; i < 4; i++){ int nx = p.x + dx[i]; int ny = p.y + dy[i]; if(nx < 1 || nx > n || ny < 1 || ny > m) continue; if(vis[nx][ny] || a[nx][ny] == '#') continue; cnt++; s[cnt].x = nx; s[cnt].y = ny; vis[nx][ny] = 1; op.push({nx,ny}); } } for(int i = 1; i <= cnt; i++){ ans[s[i].x][s[i].y] = cnt; } } void ok() { for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == '.') dfs(i,j); } void solve() { cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j]; ok(); int T; cin >> T; while(T--) { int x,y; cin >> x >> y; if(a[x][y] == '#') cout << -1 << endl; else cout << ans[x][y] - 1<< endl; } } signed main (){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T = 1; while(T--) solve(); return 0; //}
- 1
信息
- ID
- 297
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 239
- 已通过
- 19
- 上传者