hdu 1548 A strange lift
http://acm.hdu.edu.cn/showproblem.php?pid=1548
Here comes the problem: when you is on floor A,and you want to go to floor B,how many times at least he havt to press the button "UP" or "DOWN"?
The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,....kn.
A single 0 indicate the end of the input.
广搜bfs代码:
#include<iostream>
#include<queue>
using namespace std;
int k[210];
bool mark[210];
struct nod
{
int x,step;
}d,p;
int bfs(int a,int b,int n)
{
queue<nod> q;
mark[a]=1;
d.x=a;
d.step=0;
q.push(d);
while(!q.empty())
{
p=q.front();
q.pop();
if(p.x==b)
return 1;
d.x=p.x-k[p.x];
d.step=p.step+1;
if(d.x>=1&&!mark[d.x])
{
mark[d.x]=1;
q.push(d);
}
d.x=p.x+k[p.x];
if(d.x<=n&&!mark[d.x])
{
mark[d.x]=1;
q.push(d);
}
}
return 0;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
int a,b;
scanf("%d%d",&a,&b);
int i;
for(i=1;i<=n;i++)
scanf("%d",&k[i]);
memset(mark,0,sizeof(mark));
printf("%d\n",bfs(a,b,n)?p.step:-1);
}
return 0;
}
最短路dijkstra代码:
#include<iostream>
using namespace std;
#define MAX 210
#define INF 99999
int map[MAX][MAX];
int dis[MAX],v[MAX];
void dijkstra(int a,int n)
{
memset(v,0,sizeof(v));
int i,j,k,min;
for(i=1;i<=n;i++)
dis[i]=map[a][i];
v[a]=1;
dis[a]=0;
for(i=2;i<=n;i++)
{
min=INF;
k=a;
for(j=1;j<=n;j++)
if(!v[j]&&dis[j]<min)
{
k=j;
min=dis[j];
}
v[k]=1;
for(j=1;j<=n;j++)
if(!v[j]&&map[k][j]<INF)
{
if(dis[j]>dis[k]+map[k][j])
dis[j]=dis[k]+map[k][j];
}
}
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
int a,b,k[MAX];
scanf("%d%d",&a,&b);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=INF;
for(i=1;i<=n;i++)
{
scanf("%d",&k[i]);
if(i-k[i]>=1)
map[i][i-k[i]]=1;
if(i+k[i]<=n)
map[i][i+k[i]]=1;
}
dijkstra(a,n);
printf("%d\n",dis[b]==INF?-1:dis[b]);
}
return 0;
}