zstu 4215 多起点bfs

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
****************************************************************/
上一篇:【转】国外程序员整理的Java资源大全


下一篇:为什么国外程序员爱用苹果Mac电脑?(转)