题目链接 P1141 01 迷宫
直接暴力的做法就是对于每一个询问都进行 bfs, 这样复杂度最坏可以达到 O(mn2), 这样显然过不了的
我们发现, 对于一个点所拓展的路径上的所有点能走的格子数是一样的!(然而我没发现)
所以我们可以 dfs 求联通块, 每个联通块里所能走的格子数是一样的
bfs 也可以
- #include<bits/stdc++.h>
- using namespace std;
- #define check(x,y) (x>0&&x<=n&&y>0&&y<=n)
- #define nx (x+dx[i])
- #define ny (y+dy[i])
- char a[1005][1005];
- int f[1005][1005]; bool v[1005][1005];
- int n, m,now;
- const int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
- int ans[1000005];
- void dfs(int x, int y, int idx){
- now++;
- f[x][y] = idx;
- for (int i = 0; i<4; i++){
- if (check(nx, ny) && !v[nx][ny] && a[x][y] != a[nx][ny]){
- v[nx][ny] = true;
- dfs(nx, ny,idx);
- }
- }
- }
- int res;
- int main(){
- scanf("%d%d", &n, &m);
- int idx = 0;
- for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++) if (!v[i][j]){
- v[i][j] = true;
- now = 0;
- dfs(i,j,idx);
- ans[idx] = now;
- idx++;
- }
- int x, y;
- for (int i = 1; i <= m; i++){
- scanf("%d%d", &x, &y);
- printf("%d\n", ans[f[x][y]]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2974873.html