洛谷 P1141 01迷宫

题意：输入迷宫，每个位置标有0或1，可以在迷宫内任意位置可以移动，但是只能移动到与自己相反的数的位置上（比如0移动到1的格子，1移动到0的格子）

给出坐标，求它能够移动到多少个格子（自己初始的格子也算一次）

思路：可以用BFS，从给定坐标开始搜索整个迷宫，记录次数，但是第一次提交时超时了，后面发现，搜索数据很大（m有100000，而且如果每个坐标都BFS那将耗费大量时间）

后面通过题解了解到，一个连通块内所有元素能到达的坐标的数量是相同的，所以每个连通块都可以通过一次搜索统一赋好值，这里我用到一个vector记录每一次访问的坐标，然后BFS结束后给

每个坐标都记录上访问的总次数

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int n, m;
string maze[2000];
int cnt;
int d[2000][2000];
vector< pair<int, int> > record;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

void bfs(int x, int y){
  queue< pair<int, int> > q;
  q.push( pair<int, int>(x, y) );
  record.clear();
  record.push_back(pair<int, int>(x, y));
  cnt = 0;

  bool flag = false;
  while( !q.empty() ){
    pair<int, int> t = q.front(); q.pop();

    for(int i=0; i<4; i++){
      int nx = dx[i] + t.first;
      int ny = dy[i] + t.second;

      if(nx >= 0 && nx < n && ny >= 0 && ny < n && maze[nx][ny] != maze[t.first][t.second] && d[nx][ny] == -1){
        cnt++;
        flag = true;
        d[nx][ny] = 0;
        q.push( pair<int, int>(nx, ny) );
        record.push_back(pair<int, int>(nx, ny));
      }
    }
  }

  if(!flag)
    cnt++;
  for(int i=0; i<record.size(); i++){
    int rx = record[i].first;
    int ry = record[i].second;
    d[rx][ry] = cnt;
  }
}

int main(){
  ios::sync_with_stdio(false);

  cin >> n >> m;
  for(int i=0; i<n; i++)
    cin >> maze[i];

  memset(d, -1, sizeof(d));
  int x, y;
  for(int k=0; k<m; k++){
    cin >> x >> y;
    x--; y--;

    if(d[x][y] != -1)
      cout << d[x][y] << endl;
    else{
      bfs(x, y);
      cout << d[x][y] << endl;
    }
  }

  return 0;
}