N - Find a way
这个专题的最后一道题目了....
应该说的是有两个人计划去KFC碰头，找出来一个最近的KFC让他们俩见面吧，应该是个比较容易的问题，不过需要注意在一个Bfs里面搜的话，别把两个人弄混乱了...........................可以在定义的时候使用一个简单的数组标记，我还是是用一个简单的三维数组标记吧，注意求的是两个人在路上用的总时间
////////////////////////////////////////////////
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
usingnamespacestd;
constintmaxn=205;
constintoo=0xfffffff;
structnode{intx,y,op;};//op等于0的时候代表是Y，1代表M
charG[maxn][maxn];
intv[maxn][maxn][2];
intM,N;
intdir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
intBfs(nodes,nodeq)
{
queue<node>Q;
intMin=oo;
Q.push(s),Q.push(q);
v[s.x][s.y][s.op]=v[q.x][q.y][q.op]=1;
while(Q.size())
{
s=Q.front();Q.pop();
if(G[s.x][s.y]=='@'&&v[s.x][s.y][0]&&v[s.x][s.y][1])
Min=min(Min,v[s.x][s.y][0]+v[s.x][s.y][1]);
for(inti=0;i<4;i++)
{
q=s;
q.x+=dir[i][0],q.y+=dir[i][1];
if(q.x>=0&&q.x<M&&q.y>=0&&q.y<N&&G[q.x][q.y]!='#'&&v[q.x][q.y][q.op]==0)
{
v[q.x][q.y][q.op]=v[s.x][s.y][s.op]+1;
Q.push(q);
}
}
}
returnMin-2;
}
intmain()
{
while(scanf("%d%d",&M,&N)!=EOF)
{
nodes,q;
inti,j;
for(i=0;i<M;i++)
{
scanf("%s",G[i]);
for(j=0;j<N;j++)
{
if(G[i][j]=='Y')
s.x=i,s.y=j,s.op=0;
if(G[i][j]=='M')
q.x=i,q.y=j,q.op=1;
}
}
memset(v,0,sizeof(v));
intans=Bfs(s,q);
printf("%d\n",ans*11);
}
return0;
} 优质内容筛选与推荐>>
1、数据结构（3）-线性表顺序结构的合并操作
2、Oracle SQL Developer 连接 MySQL
3、C语言数组篇（一）一维数组
4、关于java中设计原则总结（7）
5、Be Better , Be Better
#include<stdio.h>
#include<string.h>
usingnamespacestd;
constintmaxn=205;
constintoo=0xfffffff;
structnode{intx,y,op;};//op等于0的时候代表是Y，1代表M
charG[maxn][maxn];
intv[maxn][maxn][2];
intM,N;
intdir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
intBfs(nodes,nodeq)
{
queue<node>Q;
intMin=oo;
Q.push(s),Q.push(q);
v[s.x][s.y][s.op]=v[q.x][q.y][q.op]=1;
while(Q.size())
{
s=Q.front();Q.pop();
if(G[s.x][s.y]=='@'&&v[s.x][s.y][0]&&v[s.x][s.y][1])
Min=min(Min,v[s.x][s.y][0]+v[s.x][s.y][1]);
for(inti=0;i<4;i++)
{
q=s;
q.x+=dir[i][0],q.y+=dir[i][1];
if(q.x>=0&&q.x<M&&q.y>=0&&q.y<N&&G[q.x][q.y]!='#'&&v[q.x][q.y][q.op]==0)
{
v[q.x][q.y][q.op]=v[s.x][s.y][s.op]+1;
Q.push(q);
}
}
}
returnMin-2;
}
intmain()
{
while(scanf("%d%d",&M,&N)!=EOF)
{
nodes,q;
inti,j;
for(i=0;i<M;i++)
{
scanf("%s",G[i]);
for(j=0;j<N;j++)
{
if(G[i][j]=='Y')
s.x=i,s.y=j,s.op=0;
if(G[i][j]=='M')
q.x=i,q.y=j,q.op=1;
}
}
memset(v,0,sizeof(v));
intans=Bfs(s,q);
printf("%d\n",ans*11);
}
return0;
} 优质内容筛选与推荐>>
1、数据结构（3）-线性表顺序结构的合并操作
2、Oracle SQL Developer 连接 MySQL
3、C语言数组篇（一）一维数组
4、关于java中设计原则总结（7）
5、Be Better , Be Better