概述
题1 Catch that cow
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
大意：
农夫和牛在一个数轴上（0 ≤N，K≤ 100,000）农夫每分钟只能向前，后走一步或走到当前坐标的2倍处即2N，问到达K的最短分钟数。BFS
代码
#include"stdio.h"
#include"queue"
#include"string.h"
#define position 100005
using namespace std;
int n,k;
struct num
{
int x;
int step;
};
bool visit[position];
void bfs()
{
queue<num> steps;
num start,now,next;
memset(visit,0,sizeof(visit));
start.x=n;
start.step=0;
steps.push(start);
visit[start.x]=1;
while(!steps.empty())
{
now=steps.front();
steps.pop();
if(now.x==k)
{
printf("%dn",now.step);
return;
}
for(int i=0;i<3;i++)
{
if(i==0)
next.x=now.x+1;
else if(i==1)
next.x=now.x-1;
else if(i==2)
next.x=now.x*2;
if(next.x>=0&&next.x<position&&!visit[next.x])
{
visit[next.x]=1;
next.step=now.step+1;
steps.push(next);
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
bfs();
return 0;
}
题2 Prime path
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don’t know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
大意
输入两个四位数的质数，每次只能改变第一个数的一位，每一次改变后的数也必须是质数，问从第一个数变到第二个数最少要几步，如果不可能输出Impossible
#include"stdio.h"
#include"cstring"
#include"queue"
#include"algorithm"
using namespace std;
int n,m;
int visit[10010];
struct node
{
int x;
int step;
};
queue<node> steps;
bool check_prime(int x)
{
int i;
if(x==1||x==0)return 0;
for(i=2;i*i<=x;i++)
if(x%i==0)break;
if(i*i>x)return 1;
else return 0;
}
void bfs()
{
node start,now,next;
start.x=n,start.step=0;visit[start.x]=1;
steps.push(start);
while(!steps.empty())
{
node temp;
now=steps.front();
steps.pop();
if(now.x==m)
{
printf("%dn",now.step);
return;
}
for(int i=1;i<=9;i+=2)
{
next.x=now.x/10*10+i;
if(check_prime(next.x)&&next.x!=now.x&&!visit[next.x])
{
visit[next.x]=1;
next.step=now.step+1;
steps.push(next);
}
}
for(int i=0;i<=9;i++)
{
next.x=now.x/100*100+i*10+now.x%10;
if(check_prime(next.x)&&next.x!=now.x&&!visit[next.x])
{
visit[next.x]=1;
next.step=now.step+1;
steps.push(next);
}
}
for(int i=0;i<=9;i++)
{
next.x=now.x/1000*1000+i*100+now.x%100;
if(check_prime(next.x)&&next.x!=now.x&&!visit[next.x])
{
visit[next.x]=1;
next.step=now.step+1;
steps.push(next);
}
}
for(int i=1;i<=9;i++)
{
next.x=i*1000+now.x%1000;
if(check_prime(next.x)&&next.x!=now.x&&!visit[next.x])
{
visit[next.x]=1;
next.step=now.step+1;
steps.push(next);
}
}
}
printf("Impossiblen");
return;
}
int main()
{
int N,i;
scanf("%d",&N);
while(N--)
{
while(steps.empty()==0)steps.pop();
memset(visit,0,sizeof(visit));
scanf("%d%d",&n,&m);
bfs();
}
return 0;
}
题3 Pots
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:
FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
DROP(i) empty the pot i to the drain;
POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.
Input
On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.
Sample Input
3 5 4
Sample Output
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)
有两个容器A,B容量分别是a,b;可以对两个容器进行3种操作
1.FILL（i）将第i个容器倒满水
2.DROP（i）将第i个容器的水全部倒出，容器里没有水了
3.POUR(i,j) 将第i个容器水倒入第j个容器，倒不满就全倒进去，能倒满，就倒满为止，剩下的水依然在第一个瓶里。输入A,B瓶的容积，a,b和目标水量c，问怎样操作能使A，B其中一个容器里最终有水c。输出操作次数和操作路径
#include"stdio.h"
#include"string.h"
#include"algorithm"
#include"queue"
using namespace std;
int a,b,c,flag=0;
struct node
{
int x;
int y;
int path[100010];//path存储路径
int step;
};
int vis[1010][1010];
queue<node> Q;
void bfs()
{
node start,now,next;
start.step=0,start.x=0,start.y=0;//一开始瓶里没水
vis[start.x][start.y]=1;
Q.push(start);
while(!Q.empty())
{
now=Q.front();
Q.pop();
if(now.x==c||now.y==c)//如果A瓶或B瓶等于c瓶里的水
{
printf("%dn",now.step);
for(int i=1;i<=now.step;i++)
{
if(now.path[i]==1)printf("FILL(1)n");
else if(now.path[i]==2)printf("FILL(2)n");
else if(now.path[i]==3)printf("DROP(1)n");
else if(now.path[i]==4)printf("DROP(2)n");
else if(now.path[i]==5)printf("POUR(1,2)n");
else if(now.path[i]==6)printf("POUR(2,1)n");
}
return;
}
for(int i=1;i<=6;i++)
{
next=now;
if(i==1)next.x=a;
else if(i==2)next.y=b;
else if(i==3)next.x=0;
else if(i==4)next.y=0;
else if(i==5)
{
int k=now.x+now.y;
if(k<=b)next.x=0,next.y=k;//倒不满
else next.x=k-b,next.y=b;//能倒满
}
else if(i==6)
{
int k=now.x+now.y;
if(k<=a)next.x=k,next.y=0;
else next.x=a,next.y=k-a;
}
if(!vis[next.x][next.y])
{
vis[next.x][next.y]=1;
next.step=now.step+1;
next.path[next.step]=i;
Q.push(next);
}
}
}
flag=1;
}
int main()
{
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{ flag=0;
memset(vis,0,sizeof(vis));
while(!Q.empty())Q.pop();
bfs();
if(flag)printf("impossiblen");
}
return 0;
}
题4 Strage lift
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button “UP” , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button “DOWN” , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can’t go up high than N,and can’t go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button “UP”, and you’ll go up to the 4 th floor,and if you press the button “DOWN”, the lift can’t do it, because it can’t go down to the -2 th floor,as you know ,the -2 th floor isn’t exist.
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”?
Input
The input consists of several test cases.,Each test case contains two lines.
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.
Output
For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can’t reach floor B,printf “-1”.
Sample Input
5 1 5
3 3 1 2 5
0
Sample Output
3
有一个奇怪的电梯，它有从1到N层，每一层都有一个数ki，当前这一层只能向上或向下移动ki层。如果你在第3层，第三层的ki比如是2，那么你可以移动到3+2=5层或移动到3-2=1层，如果你在第A层，你怎么按最少的按钮到达第B层呢？输入N,A,B以及每一层的ki。输出最小的操作数
#include"stdio.h"
#include"queue"
#include"string.h"
using namespace std;
const int MAX=220;
int n,a,b,flag;
int f[220],vis[220];
struct node
{
int ki;
int step;
int num;
};
void bfs()
{
int i;
queue<node> Q;
node start,aa,bb;
start.step=a,start.ki=f[a],start.num=0;
vis[start.step]=1;
Q.push(start);
while(!Q.empty())
{
aa=Q.front();
Q.pop();
if(aa.step==b)
{
printf("%dn",aa.num);
return;
}
for(i=0;i<2;i++)
{
bb=aa;
if(i==0)
{
bb.step+=bb.ki;
bb.ki=f[bb.step];
}
else if(i==1)
{
bb.step-=bb.ki;
bb.ki=f[bb.step];
}
if(bb.step>=1&&bb.step<=n&&!vis[bb.step])
{
bb.num=aa.num+1;
vis[bb.step]=1;
Q.push(bb);
}
}
}
flag=1;
}
int main()
{
int i;
while(scanf("%d%d%d",&n,&a,&b)&&n!=0)
{
flag=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)scanf("%d",&f[i]);
bfs();
if(flag)printf("-1n");
}
}
题5 Nightmare
Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.
Given the layout of the labyrinth and Ignatius’ start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.
Here are some rules:
1. We can assume the labyrinth is a 2 array.
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
3. If Ignatius get to the exit when the exploding time turns to 0, he can’t get out of the labyrinth.
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can’t use the equipment to reset the bomb.
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.
Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius’ start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius’ target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.
Output
For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.
Sample Input
3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1
Sample Output
4
-1
13
#include"stdio.h"
#include"cstring"
#include"queue"
using namespace std;
int map[10][10],m,n,flag,vis[10][10];
int sx,sy,ex,ey;
struct node
{
int min;
int zd;
int x,y;
};
void bfs()
{
int i,j,next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue<node> Q;
node start,aa,bb;
start.min=0,start.x=sx,start.y=sy,start.zd=6;
Q.push(start);
while(!Q.empty())
{
aa=Q.front();
Q.pop();
if(aa.x==ex&&aa.y==ey&&aa.zd>0)
{
printf("%dn",aa.min);
return;
}
for(i=0;i<4;i++)
{ bb=aa;
bb.x+=next[i][0];
bb.y+=next[i][1];
bb.zd=aa.zd-1;
bb.min=aa.min+1;
if(((map[bb.x][bb.y]==4&&!vis[bb.x][bb.y])||map[bb.x][bb.y]==1
||map[bb.x][bb.y]==3)&&bb.zd>0&&bb.x>=0&&bb.x<n&&bb.y>=0&&bb.y<m)
{
if(map[bb.x][bb.y]==4)
{
bb.zd=6;
vis[bb.x][bb.y]=1;
}
Q.push(bb);
}
}
}
flag=1;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==2)sx=i,sy=j;
if(map[i][j]==3)ex=i,ey=j;
}
flag=0;memset(vis,0,sizeof(vis));
bfs();
if(flag)printf("-1n");
}
}
最后
以上就是现代百合为你收集整理的BFS之五道题的全部内容，希望文章能够帮你解决BFS之五道题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复