首页 > 代码库 > Ural 1096-Get the Right Route Plate!（bfs）
Ural 1096-Get the Right Route Plate!（bfs）
1096. Get the Right Route Plate!
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Everybody who had ridden a Ekaterinburg bus could notice that on the inner side of the plate with the number of the route there was a number of another route.
One day the driver of a new bus came to the storehouse and found that there was no plate with the number of the route he had been assigned to ride. The storekeeper simply gave him a random plate and advised to change it for a plate from another bus. But the drivers who had the necessary plates did not need the plate given by the storekeeper. Any driver will agree to change his plate for another only if this plate has the number of his route. Help the new driver to find a shortest sequence of changes that will enable him to get a plate with the number of his route.
Input
The first line contain the number K ≤ 1000 of the acting buses (excluding the new bus). The buses are numbered from 1 to K. The next K lines contain the number of the route of the corresponding bus and the number on the other side of its plate. Numbers of routes are integers from 1 to 2000.
The last line of the input contains the number of the route of the new bus and the numbers on the plate given by the storekeeper.
Output
The first line of the output should contain the word IMPOSSIBLE if it is impossible to get the needed number by a sequence of changes otherwise it should contain the least necessary number of changes M > 0 followed by an M lines that contain sequentially numbers of buses (not routes!) with drivers of which the plates must be changed. If there are several solutions, you can output any one.
Sample
| input | output |
|---|---|
4 8 5 5 4 7 4 1 5 4 1 8 | 2 4 2 |
题意：给出k个车牌，正反两面都有号码，然后给你一个车牌，还有一个路线号，你的任务是和别人交换车牌，来使车牌上的号码和你的路线号相同（正反面有一个相同即可）交换规则是你的牌子上面的号码要有和别人的牌子正面的号码相同的，求最小交换次数，然后打印路径（即和每个车牌交换的路径 车牌编号从1--k）bfs+记录路径即可。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <list>
using namespace std;
const int maxn=2000011;
const int INF=1<<29;
bool vis[2010][2010];
struct node{
int x,y,pre,cur,step;
}que[maxn];
int m,s,e,xx[maxn],yy[maxn];
void bfs(int x,int y,int goal)
{
s=e=0;int pos;
memset(vis,0,sizeof(vis));
node t,f;
t.step=0;t.x=x;t.y=y;t.pre=0;t.cur=0;
vis[t.x][t.y]=1;
que[e++]=t;
while(s<e)
{
f=que[s];pos=s;s++;
if(f.x==goal||f.y==goal)
{
stack <int> ss;
printf("%d\n",f.step);
int tem=pos;
for(int i=0;i<f.step;i++)
{
ss.push(que[tem].cur);
tem=que[tem].pre;
}
while(!ss.empty())
{
printf("%d\n",ss.top());
ss.pop();
}
return ;
}
for(int i=1;i<=m;i++)
{
if(xx[i]==f.x||xx[i]==f.y)
{
t.x=xx[i];
t.y=yy[i];
t.pre=pos;
t.cur=i;
t.step=f.step+1;
if(!vis[t.x][t.y])
{
vis[t.x][t.y]=1;
que[e++]=t;
}
}
}
}
puts("IMPOSSIBLE");
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&xx[i],&yy[i]);
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
bfs(b,c,a);
return 0;
}
Ural 1096-Get the Right Route Plate!（bfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。