Alien Security

原题

Language:
Alien Security
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 2898 Accepted: 1064
Description

You are in charge of security at a top-secret government research facility. Recently your government has captured a live extra-terrestrial (ET) life form, and is hosting an open day for fellow researchers. Of course, not all the guests can be trusted, so they are assigned different security clearance levels. Only guests with a level 5 rating will be allowed into the lab where the extra-terrestrial is being held; other than that, everyone is free to roam throughout the rest of the facility. Each room in the facility is connected via one-way airlocks, so that you can pass through the door in only one direction.

To protect your precious ET you will put in place enhanced security measures (in the form of armed guards) on the route leading to the room containing the ET, but not in the room itself ?the guards do not have sufficient clearance to enter the room containing the ET.

The guards will check the identity and the security rating of all guests trying to pass through the room in which they are stationed, so you would like to place the guards where they will cause the minimum amount of irritation to the guests who have no intention of visiting the ET. The room where the guards must be placed thus satisfies the following two conditions:

In order to get to the room containing the ET, the guests must pass through the room containing the guards;
There is no other room with this property that is closer to the room containing the ET ?remember, the guards cannot be placed in the room containing the ET itself.

The diagram below illustrates one possible map of your facility:

Note that placing the guards in room 2 would satisfy the first condition, but room 3 is closer to the ET, so the guards must be placed in room 3.
Input

All guests enter through room 0, the entrance to your facility. Your program accepts a sequence of lines containing integers. The first line consists of two integers: the number of rooms, and the room in which the ET is being held (out of his own free will, of course).

The rest of the input is a sequence of lines consisting of only two integers, specifying where the airlock-doors are located. The first number on these lines specifies the source room, and the second the destination room. Remember: you can pass only from the source room to the destination room.
Output

The output of your program consists only of a single line:

Put guards in room N.

where N is the room you’ve decided to place the guards.
Sample Input

9 4
0 2
2 3
3 4
5 3
5 4
3 6
6 5
6 7
6 8
4 7
0 1
1 7
7 0

Sample Output

Put guards in room 3.

题目大意

研究机构的每个房间由单向密封过渡仓连接，所以进去只能一个方向通过。

设置守卫室的位置，使其满足一下条件：

要到达et位置，客人必须通过守卫室的房间
没有其他房间更接近放有et的房间，守卫室不能设在et所在的位置

所有客人必须首先进入0号房间，这是入口

程序输入有多行，第一行有两个整数：房间的数目，et所在的位置

其余各行也有两个整数，指明通向，第一个源房间，第二个目标房间，单向。

程序输出只有一行 Put guards in room N. N是守卫室的位置

题目包含多组数据，第一行是N，表示N组测试数据，每组数据格式与问题描述一样，组数据间有一个空行

算法分析

本题需要用到广度和深度搜索.

构造邻接矩阵
使用数组data表示研究机构的邻接矩阵:
```
const int MaxN = 100;
bool data[MaxN][MaxN];
```
房间数目是n,ET所在房间是变量et;
另外,因为要输入一空行区别组间数据,所以用字符串处理,用到sscanf函数.
广度优先搜索,搜索各个房间到et的房间的最近距离
如果站在et的房间看,将过渡舱反一下,就成了单源最短路径问题(Shortest Path Faster Algorithm,SPFA)问题,这时用广搜能得到很高的效率.
```
void shortest()
```
实现bfs(广搜)的重要一步是建立队列,可以使用链表,数组,C++的string和Vector模拟队列,最简单的是用queue()函数:
```
queue<int> q;
```
从当前房间x向四周扩展,如果到房间i有通路,且能够获得更短的距离,则经过房间i,并将i入栈.
枚举
去掉房间i后还能到达et房间的就舍去.

程序代码

#include <iostream>
#include <string.h>
#include <queue>
#include <memory.h>
using namespace std;

const int MaxN = 100;
bool data[MaxN][MaxN];    //表示邻接的矩阵
bool used[MaxN];        //dfs搜索标志,表示已经搜索过了
int n, et;                //房间数和机器人所在的房间 
int dis[MaxN];            //表示从其它房间到et房间的距离
//广度优先搜索
void shortest()
{
    queue<int> q;    //搜索队列
    q.push(et);        //起始搜索位置
    dis[et]=0;
    int x;
    while(!q.empty())
    {
        x=q.front();        //取头结点
        q.pop();
        for(int i=0;i<n;i++)
        {
            //从et房间出发是逆向行走
            //经过房间x到et比经过i到et房间更近
            if(data[i][x]&&dis[x]<dis[i])
            {
                q.push(i);
                dis[i]=dis[x]+1;
            }
        }
    }
}
//深搜
bool search(int i)
{
    if(i==et)    return true;    //成功到达et的标志
    used[i]=true;
    //搜索下一个出口
    for(int j=0;j<n;++j)
    {
        if(!used[j]&&data[i][j])
            if(search(j))
                return true;
    }
    return false;
}
int main()
{
    int cases;//几组数据
    int room;
    int d;
    scanf("%d",&cases);
    for(int l=0;l<cases;++l)
    {
        scanf("%d%d\n",&n,&et);        //"\n"不能少 
        memset(data,0,sizeof(data));
        for(int m=0;m<MaxN;m++)
        {
            dis[m]=INT_MAX;
        }
        char line[10];
        int a,b;
        while(gets(line))
        {
            if(strcmp(line,"")==0) break;
            sscanf(line,"%d%d",&a,&b);
            data[a][b]=true;
        }
        shortest();    
    //枚举,除房间et外,逐个房间设置守卫,搜索最优解
    room=0;
    d=dis[0];
    for(int i=1;i<n;i++)
    {
        if(i==et)    continue;
        memset(used,0,sizeof(used));
        //设置在i房间,就是将i拿掉
        used[i]=1;
        //从入口0不能到达et,说明0是必经之路
        //而且能获得到房间et更短的距离
        if(!search(0)&&dis[i]<d)
        {
            room=i;
            d=dis[i];    
        }    
    }
    if(l) cout<<endl;
        cout<< "Put guards in room "<<room<<"."<<endl;    
    }
    return 0;
}

总结

首先,这是第一次接触bfs,bfs一般用队列.
其次,了解了sscanf这个函数
sscanf() - 从一个字符串中读进与指定格式相符的数据.
同时,消除了一个误区,本以为memset可以整体赋值任何数据,结果百度后发现:

memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个字节的内容全部设置为ch指定的ASCII值，第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作，其返回值为指向s的指针。

但可以用这个函数清零:

memset(used,0,sizeof(used));