我tm到现在还需要刷这种水搜索...我退役吧。

但就是搜索弱嘛 补一补嘛qwq

 

题目大意：给你一张地图与许多询问，每次询问求这个点所在联通块的点的个数。

所以这个题目的本质就是在求联通块。可以联想到那天测试的题，把看似bfs的题写成dfs。

注意：联通块数组开小了导致RE===

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
           5  6 using namespace std; 7  8 int n,m,cnt,tmp; 9 int dx[5]={
   0,1,-1,0,0};10 int dy[5]={
   0,0,0,1,-1};11 int block[1010][1010],mark[1010*1010];12 char qwq[2000],mapp[2000][2000];13 bool vis[2000][2000];14 15 bool pd(int x,int y,int xx,int yy)16 {17     if(mapp[x][y]=='1'&&mapp[xx][yy]=='0') return 1;18     if(mapp[x][y]=='0'&&mapp[xx][yy]=='1') return 1;19     return 0;20 }21 22 bool valid(int x,int y)23 {24     if(x>=1&&x<=n&&y>=1&&y<=n) return 1;25     return 0;26 }27 28 void dfs(int nowx,int nowy,int pos)29 {30     vis[nowx][nowy]=1;mark[pos]++;block[nowx][nowy]=pos;31     for(int i=1;i<=4;i++)32         if(valid(nowx+dx[i],nowy+dy[i])&&pd(nowx,nowy,nowx+dx[i],nowy+dy[i])&&!vis[nowx+dx[i]][nowy+dy[i]])33             dfs(nowx+dx[i],nowy+dy[i],pos);34 }35 36 int main()37 {38     scanf("%d%d",&n,&m);39     for(int i=1;i<=n;i++)40     {41         scanf("%s",qwq+1);42         for(int j=1;j<=n;j++) mapp[i][j]=qwq[j];43     }44     for(int i=1;i<=n;i++)45         for(int j=1;j<=n;j++)46             if(!block[i][j])47             {48                 cnt++;49                 dfs(i,j,cnt);50             }51     for(int i=1;i<=m;i++)52     {53         int x=0,y=0;54         scanf("%d%d",&x,&y);55         printf("%d\n",mark[block[x][y]]);56     }57     return 0;58 }