A strange lift
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8989 Accepted Submission(s): 3404
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has 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.
# include <iostream>
# include <queue>
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
using namespace std;
int n,a,b;
int hash[210];
int s[210];
int BFS( )
{
int now,next,flag = 0;
queue<int>q;
q.push(a);
memset(hash,0,sizeof(hash));
hash[a] = 0;
while(!q.empty())
{
now=q.front();
q.pop();
if(now==b)
{
flag=1;
break;
}
next=now-s[now];
if(next>0&&!hash[next])
{
q.push(next);
hash[next]=hash[now]+1;
}
next=now+s[now];
if(next<=n&&!hash[next])
{
q.push(next);
hash[next]=hash[now]+1;
}
}
if(flag)
return(hash[b]);
else
return -1;
}
int main()
{
while(scanf("%d",&n)&&n)
{
int flag,i;
scanf("%d%d",&a,&b);
for(i=1; i<=n;i++)
scanf("%d",&s[i]);
flag=BFS();
printf("%d
",flag);
}
return 0;
}
最短路:
#include<stdio.h>
#include<string.h>
#define M 1000000
int n,a,b,dis[201],map[202][201],vit[210];
void dijkstra()
{
int i,j,k,min;
for(i=1; i<=n; i++)
dis[i]=map[a][i];
memset(vit,0,sizeof(vit));
dis[a]=0;
for(i=1; i<n; i++)
{
min=M;
for(j=1; j<=n; j++)
{
if(!vit[j] && dis[j]<min)
{
min=dis[j];
k=j;
}
}
if(min==M)
break;
vit[k]=1;
for(j=1; j<=n; j++)
if(!vit[j] && map[k][j]+dis[k]<dis[j])
dis[j]=dis[k]+map[k][j];
}
}
int main()
{
int i,j,f[201];
while(scanf("%d",&n),n)
{
scanf("%d%d",&a,&b);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
map[i][j]=M;
}
for(i=1; i<=n; i++)
{
scanf("%d",&f[i]);
if(i+f[i]<=n)
map[i][i+f[i]]=1;
if(i-f[i]>=1)
map[i][i-f[i]]=1;
}
dijkstra();
if(dis[b]<M)
printf("%d
",dis[b]);
else
puts("-1");
}
return 0;
}