2020-03-10（洛谷P1141 01迷宫）

写到吐血的一道题，其实就是再dfs上加了一个优化，变成了联通快，也可以叫做记忆化搜索；
1. 如果当前的点不属于任何一个连通块，就把这个点当做新的连通块的起点，dfs，寻找他能到达的最多块数， 并且把和他相连所有点都映射到该点处。
2.如果当前的点被搜索过，就说明他一定在一个联通块中，就把这个连通块的起始位置找到，输出数量即可。

#include <cstdio>
#include <iostream>
#include <cstring>
 using namespace std;

const int N = 1010;
int n, m;
char g[N][N];
bool st[N][N];
int asw;
int liantong[N][N];
int liantong_x[N][N];
int liantong_y[N][N];



//queue<PII> q;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y,int startx, int starty)
{
    asw ++;
    st[x][y] = true;
    liantong_x[x][y] =  startx,
    liantong_y[x][y] = starty;
            for(int i=0; i<4; i++)
        {
            int xx = x + dx[i];   int yy = y + dy[i];
            if(!st[xx][yy] && g[xx][yy] != g[x][y] && xx >= 0 && xx < n && yy >= 0 && yy < n) 
              {
                dfs(xx, yy, startx, starty);
              }
        }

    return asw;
 } 

 int main()
 {
    scanf("%d%d", &n, &m);
//  string s;
    for(int i=0; i<n; i++)
    {
          scanf("%s", g[i]);
    }


         
    while(m--)
    {
//      memset(st, 0, sizeof(st));
//      memset(liantong_x, -1, sizeof(liantong_x));
//      memset(liantong_y, -1, sizeof(liantong_y));
        asw = 0;
        int a, b;
        scanf("%d%d", &a, &b);
        if(st[a-1][b-1]) cout<<liantong[liantong_x[a-1][b-1] ][liantong_y[a-1][b-1] ]<<endl;
        else 
        {

            liantong[a-1][b-1] = dfs(a-1, b-1, a-1, b-1);

            cout<<liantong[a-1][b-1]<<endl;
         }
    }
 }