Luogu P1141 01迷宫【搜索/dfs】By cellur925

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

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

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

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

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

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cstring> 

 using namespace std;

 int n,m,cnt,tmp;

 int dx[]={,,-,,};

 int dy[]={,,,,-};

 int block[][],mark[*];

 char qwq[],mapp[][];

 bool vis[][];

 bool pd(int x,int y,int xx,int yy)

 {

     if(mapp[x][y]==''&&mapp[xx][yy]=='') return ;

     if(mapp[x][y]==''&&mapp[xx][yy]=='') return ;

     return ;

 }

 bool valid(int x,int y)

 {

     if(x>=&&x<=n&&y>=&&y<=n) return ;

     return ;

 }

 void dfs(int nowx,int nowy,int pos)

 {

     vis[nowx][nowy]=;mark[pos]++;block[nowx][nowy]=pos;

     for(int i=;i<=;i++)

         if(valid(nowx+dx[i],nowy+dy[i])&&pd(nowx,nowy,nowx+dx[i],nowy+dy[i])&&!vis[nowx+dx[i]][nowy+dy[i]])

             dfs(nowx+dx[i],nowy+dy[i],pos);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

     {

         scanf("%s",qwq+);

         for(int j=;j<=n;j++) mapp[i][j]=qwq[j];

     }

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             if(!block[i][j])

             {

                 cnt++;

                 dfs(i,j,cnt);

             }

     for(int i=;i<=m;i++)

     {

         int x=,y=;

         scanf("%d%d",&x,&y);

         printf("%d\n",mark[block[x][y]]);

     }

     return ;

 }

巴特西

Luogu P1141 01迷宫【搜索/dfs】By cellur925

最新文章

热门文章