POJ 3278
题意是一个农夫在一维空间内找一头奶牛，
农夫的位置是x 奶牛的位置是y
农夫每次可以走到x+1或x-1或者2*x；
问最少需要多少次才可以找到奶牛。
思路：水题，裸的一道BFS，唯一的坑就是数组开10W会RE。具体不多说，上代码
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int a[1000005];
void bfs(int s,int e)
{
queue<int> q;
q.push(s);
memset(a,0,sizeof(a));
a[s]=0;
while(q.size())
{
int p=q.front();
q.pop();
if(p==e)
break;
if(p<e)
{
if(a[p+1]==0)
{
q.push(p+1);
a[p+1]=a[p]+1;
}
if(a[2*p]==0)
{
q.push(2*p);
a[2*p]=a[p]+1;
}
if(p>0&&a[p-1]==0)
{
q.push(p-1);
a[p-1]=a[p]+1;
}
}
else
{
if(a[p-1]==0&&p>0)
{
q.push(p-1);
a[p-1]=a[p]+1;
}
}
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
bfs(n,k);
printf("%d\n",a[k]);
}
}
hdu 1372
题意：
从一个位置控制马跳到终点最少需要多少步。
裸的8方向BFS，不多说，上代码
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> P;
int sx,sy;
int ex,ey;
int d[10][10];
bool vis[10][10];
int x[8]={1,1,2,2,-1,-1,-2,-2};
int y[8]={2,-2,1,-1,2,-2,1,-1};
int bfs()
{
queue<P> q;
q.push(P(sx,sy));
d[sx][sy]=0;
while(q.size())
{
P p=q.front();
q.pop();
if(p.first==ex&&p.second==ey)
break;
for(int i=0;i<8;i++)
{
int nx=p.first+x[i];
int ny=p.second+y[i];
if(nx>=0&&ny>=0&&nx<8&&ny<8&&vis[nx][ny]==0)
{
q.push(P(nx,ny));
d[nx][ny]=d[p.first][p.second]+1;
vis[nx][ny]=1;
}
}
}
return d[ex][ey];
}
int main()
{
char s[5];
char e[5];
while(scanf("%s %s",s,e)!=EOF)
{
//cout<<s<<endl;
sx=s[0]-‘a‘;
sy=s[1]-‘1‘;
ex=e[0]-‘a‘;
ey=e[1]-‘1‘;
//cout<<sx<<" "<<sy<<endl;
//cout<<ex<<" "<<ey<<endl;
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
int k=bfs();
printf("To get from %s to %s takes %d knight moves.\n",s,e,k);
}
}
hdu 1072
题意：
身上带着一个炸弹能不能走到终点
2是起点，3是终点，1是路，0是墙，4是把炸弹时间回归一开始的状态。
这个题目需要注意的是有些路是可以重复走的，当你现在炸弹的时间比这条路以前走过的时候的炸弹时间长得时候，就可以重复走。
贴上代码
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
int a[8][8];
int b[8][8];
int c[8][8];
int n,m,t;
int x1[4]={1,0,-1,0},y1[4]={0,1,0,-1};
int i1,i2,j1,j2;
int flag;
int k;
int bfs()
{
queue<P> q;
q.push(P(i1,j1));
while(!q.empty())
{
P p=q.front();q.pop();
if(a[p.first][p.second]==4) b[p.first][p.second]=6;
if(p.first==i2&&p.second==j2) break;
for(int i=0;i<4;i++)
{
int nx=p.first+x1[i],ny=p.second+y1[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&a[nx][ny]!=0&&b[nx][ny]<b[p.first][p.second]-1)
{
q.push(P(nx,ny));
b[nx][ny]=b[p.first][p.second]-1;
//printf("%d-%d-%d\n",nx,ny,b[nx][ny]);
c[nx][ny]=c[p.first][p.second]+1;
}
}
}
return c[i2][j2];
}
int main()
{ int L;
scanf("%d",&L);
while(L--)
{ scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
memset(b,0,sizeof(b));
flag=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==2)
{i1=i;
j1=j;}
if(a[i][j]==3)
{
i2=i,j2=j;
}
}
b[i1][j1]=6;
flag=bfs();
if(flag==0)
printf("-1\n");
else printf("%d\n",flag);
}
}
HDU 1180
题意是求从起点到终点的最短距离，然后其中有一些楼梯每秒都会变化一次，
我处理的方法是，竖着的楼梯为1，然后横着的为0，判断到达这的时间是否为奇数，如果是奇数，就取非。
然后就是水的BFS了，
上代码
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
char a[25][25];
bool vis[25][25];
int d[25][25];
int x[4]={1,0,-1,0};
int y[4]={0,1,0,-1};
int n,m;
void bfs(int sx,int sy)
{
queue<P> q;
q.push(P(sx,sy));
memset(d,-1,sizeof(d));
memset(vis,0,sizeof(vis));
vis[sx][sy]=1;
d[sx][sy]=0;
while(q.size())
{
P p=q.front();
q.pop();
vis[p.first][p.second]=0;
for(int i=0;i<4;i++)
{
int nx=p.first+x[i];
int ny=p.second+y[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&a[nx][ny]!=‘*‘)
{
bool flag=0;
if(a[nx][ny]!=‘.‘&&a[nx][ny]!=‘T‘)
{
bool pp;
if(a[nx][ny]==‘|‘)
pp=1;
else pp=0;
if(d[p.first][p.second]%2==1)
pp=!pp;
if(pp&&x[i]!=0)
nx+=x[i];
else if(!pp&&y[i]!=0)
ny+=y[i];
else
{
flag=1;
if(x[i]!=0)
nx+=x[i];
else ny+=y[i];
}
}
if(a[nx][ny]!=‘*‘)
{
if(d[nx][ny]==-1||d[nx][ny]>d[p.first][p.second]+1+flag)
{
d[nx][ny]=d[p.first][p.second]+1+flag;
if(vis[nx][ny]==0)
{
vis[nx][ny]=1;
q.push(P(nx,ny));
}
}
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%s",a[i]);
int nx,ny;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(a[i][j]==‘S‘)
bfs(i,j);
else if(a[i][j]==‘T‘)
{
nx=i;ny=j;
}
}
printf("%d\n",d[nx][ny]);
}
}
hdu 2579
题意是从Y到G最少需要多少步，墙会在K的倍数的时间的时候消失。
如果不能到达输出Please give me another chance!。
普普通通的BFS，就是在到达墙的时候判断能否在某个特定的时间穿墙而过，
有一组数据特别坑，就是当你旁边只剩下墙的时候，你是不能走了的，因为你不能在原地等待，所以这个时候你是应该直接输出不能。
不多说。贴上代码。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<iostream>
#define INF 10000000
using namespace std;
char a[105][105];
int b[105][105];
int x[4]={1,0,-1,0};
int y[4]={0,1,0,-1};
typedef pair<int,int> P;
int n,m,k;
void bfs(int x1,int y1)
{
queue<P> q;
q.push(P(x1,y1));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
b[i][j]=INF;
b[x1][y1]=0;
while(q.size())
{
P p=q.front();
q.pop();
bool flag=0;
for(int i=0;i<4;i++)
{
int nx=p.first+x[i];
int ny=p.second+y[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m&&a[nx][ny]!=‘#‘)
{
flag=1;
break;
}
}
for(int i=0;i<4;i++)
{
int nx=p.first+x[i];
int ny=p.second+y[i];
if(nx>=0&&ny>=0&&nx<n&&ny<m)
{
if(a[nx][ny]!=‘#‘&&b[nx][ny]>b[p.first][p.second]+1)
{
b[nx][ny]=b[p.first][p.second]+1;
q.push(P(nx,ny));
}
else
{
if(k%2==1)
{
int out=b[p.first][p.second]/k;
out++;
if(out%2==b[p.first][p.second]%2)
out++;
out*=k;
if(b[nx][ny]>out&&(flag==1||out==b[p.first][p.second]+1))
{
b[nx][ny]=out;
q.push(P(nx,ny));
}
}
else if(b[p.first][p.second]%2==1)
{
int out=b[p.first][p.second]/k;
out++;
out*=k;
if(b[nx][ny]>out&&(flag==1||out==b[p.first][p.second]+1))
{
b[nx][ny]=out;
q.push(P(nx,ny));
}
}
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;i++)
scanf("%s",a[i]);
int xn,yn,ex,ey;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(a[i][j]==‘Y‘)
{
xn=i;
yn=j;
}
if(a[i][j]==‘G‘)
{
ex=i;
ey=j;
}
}
bfs(xn,yn);
if(b[ex][ey]==INF)
printf("Please give me another chance!\n");
else printf("%d\n",b[ex][ey]);
}
}
hdu 1253
题意：
在一个三维空间内从起点到终点的最短时间，时间有限制。
水的BFS，唯一就是比平常的二维多了一维。
不多说，上代码。
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct P{
int zz,nn,mm;
};
int a[55][55][55];
int vis[55][55][55];
int c[55][55][55];
int x[4]={1,0,-1,0},y[4]={0,1,0,-1},z1[2]={1,-1};
int n,m,z;
int bfs(int t)
{
queue <P> q;
P s;
s.zz=0;s.nn=0;s.mm=0;
q.push(s);
c[0][0][0]=0;
while(q.size())
{
P p=q.front();
q.pop();
if(c[p.zz][p.nn][p.mm]>=t) break;
if(p.zz==z-1&&p.nn==n-1&&p.mm==m-1)
{
break;
}
for(int i=0;i<2;i++)
{
int nz=p.zz+z1[i];
int nx=p.nn,ny=p.mm;
if(nz>=0&&nz<z&&a[nz][nx][ny]==0&&vis[nz][nx][ny]==0)
{
vis[nz][nx][ny]=1;
P nm;
nm.zz=nz;nm.nn=nx;nm.mm=ny;
q.push(nm);
c[nz][nx][ny]=c[p.zz][p.nn][p.mm]+1;
}
}
for(int i=0;i<4;i++)
{
int nx=p.nn+x[i];
int ny=p.mm+y[i];
int nz=p.zz;
if(nx>=0&&nx<n&&ny>=0&&ny<m&&vis[nz][nx][ny]==0&&a[nz][nx][ny]==0)
{
vis[nz][nx][ny]=1;
P nm;
nm.zz=nz;nm.nn=nx;nm.mm=ny;
q.push(nm);
c[nz][nx][ny]=c[p.zz][p.nn][p.mm]+1;
}
}
}
return c[z-1][n-1][m-1];
}
int main()
{ int t;
scanf("%d",&t);
while(t--)
{ int T;
scanf("%d%d%d%d",&z,&n,&m,&T);
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
for(int i=0;i<z;i++)
for(int j=0;j<n;j++)
for(int l=0;l<m;l++)
scanf("%d",&a[i][j][l]);
int k=bfs(T);
if(k==0)
printf("-1\n");
else printf("%d\n",k);
}
}
原文：http://blog.csdn.net/u012896700/article/details/21987595