zstu 4215 多起点bfs

时间：2021-04-17 09:10:18
input

n m 　　1<=n,m<=1000

n*m的地图，全为大写字母

7 10

WWWWWCCDEW

WWWWCCEEEW

WTWWWCCCCW

WWFFFFFFWW

WWFAAAAFWW

WWFABCAFFW

WWFAAAAFWW
output
从W到每种字母跨过最少的其它字母个数，如从W到A只跨过一种字母F
A 1

B 2

C 0

D 1

E 0

F 0

T 0
做法：把每个W的连通块当成起点依次进队进行bfs
 #include <bits/stdc++.h>

 #define MAX 1000000

 #define LL long long

 using namespace std;

 int cas=,T,n,m,v[][],idn,mind[],idp[MAX+][];//idp表示连通块起点

 char s[][],id[MAX+];

 int vis[MAX+];

 void dfs(int x,int y,char& c,int &id)//连通块标id

 {

     if(x>=n||y>=m||x<||y<||v[x][y]!=-||s[x][y]!=c) return;

     v[x][y]=id;

     dfs(x+,y,c,id);

     dfs(x-,y,c,id);

     dfs(x,y+,c,id);

     dfs(x,y-,c,id);

     dfs(x+,y+,c,id);

     dfs(x-,y-,c,id);

     dfs(x+,y-,c,id);

     dfs(x-,y+,c,id);

 }

 queue<int>q[];

 void dfs(int x,int y,int &k,int d)//查找相邻接的连通块

 {

     if(x<||y<||x>=n||y>=m) return;

     if(v[x][y]!=k) { q[d].push(v[x][y]);return; }//入队列

     if(!s[x][y]) return;

     s[x][y]=;

     dfs(x+,y,k,d);

     dfs(x-,y,k,d);

     dfs(x,y+,k,d);

     dfs(x,y-,k,d);

     dfs(x+,y+,k,d);

     dfs(x-,y-,k,d);

     dfs(x+,y-,k,d);

     dfs(x-,y+,k,d);

 }

 void bfs()

 {

     memset(vis,-,sizeof(vis));

     int d=,step=;

     while(!q[].empty()) q[].pop();

     while(!q[].empty()) q[].pop();

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

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

             if(s[i][j]&&s[i][j]=='W') { dfs(i,j,v[i][j],d);vis[v[i][j]]=; }

     while(!q[d].empty())//两个队列bfs，一个队列是一步

     {

         while(!q[d].empty())

         {

             int u=q[d].front();q[d].pop();

             if(vis[u]!=-) continue;              //标记

             dfs(idp[u][],idp[u][],u,d^);

             vis[u]=step;

         }

         step++;

         d^=;

     }

 //  for(int i=0;i<idn;i++) printf("%d %c %d\n",i,id[i],vis[i]);

 }

 void process()

 {

     idn=;

     for(int i=;i<n;i++)     //给每个连通块标>=0的id

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

             if(v[i][j]==-) { dfs(i,j,s[i][j],idn);idp[idn][]=i;idp[idn][]=j;id[idn++]=s[i][j]; }

 //  for(int i=0;i<n;i++,printf("\n")) for(int j=0;j<m;j++) printf("%02d ",v[i][j]);

 }

 int main()

 {

 //  freopen("in","r",stdin);

     //scanf("%d",&T);

     while(scanf("%d%d",&n,&m)==)

     {

         for(int i=;i<n;i++) { scanf("%s",s[i]);memset(v[i],-,sizeof(int)*m); }     //input

         process();

         bfs();

         for(int i=;i<;i++) mind[i]=MAX;             //查找每个大写字母的最小值

         for(int i=;i<idn;i++) mind[id[i]-'A']=min(mind[id[i]-'A'],vis[i]);

         for(int i=;i<;i++) if(mind[i]&&mind[i]<MAX) printf("%c %d\n",i+'A',mind[i]-);

     }

     //printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);

     return ;

 }

 /**************************************************************

     Problem: 4215

     User: 15xss282

     Language: C++

     Result: Accepted

     Time:364 ms

     Memory:21028 kb

 ****************************************************************/

相关文章