UVa 208:Firetruck,双向搜索进行剪枝

题目链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=144

类型: 回溯法

原题:

The Center City fire department collaborates with the transportation department to maintain maps of the city which reflects the current status of the city streets. On any given day, several streets are closed for repairs or construction. Firefighters need to be able to select routes from the firestations to fires that do not use closed streets.

Central City is divided into non-overlapping fire districts, each containing a single firestation. When a fire is reported, a central dispatcher alerts the firestation of the district where the fire is located and gives a list of possible routes from the firestation to the fire. You must write a program that the central dispatcher can use to generate routes from the district firestations to the fires.

Input

The city has a separate map for each fire district. Streetcorners of each map are identified by positive integers less than 21, with the firestation always on corner #1. The input file contains several test cases representing different fires in different districts.

The first line of a test case consists of a single integer which is the number of the streetcorner closest to the fire.

The next several lines consist of pairs of positive integers separated by blanks which are the adjacent streetcorners of open streets. (For example, if the pair 4 7 is on a line in the file, then the street between streetcorners 4 and 7 is open. There are no other streetcorners between 4 and 7 on that section of the street.)

The final line of each test case consists of a pair of 0's.

Output

For each test case, your output must identify the case by number (CASE #1, CASE #2, etc). It must list each route on a separate line, with the streetcorners written in the order in which they appear on the route. And it must give the total number routes from firestation to the fire. Include only routes which do not pass through any streetcorner more than once. (For obvious reasons, the fire department doesn't want its trucks driving around in circles.)

Output from separate cases must appear on separate lines.

The following sample input and corresponding correct output represents two test cases.

题目大意:

城市消防中心与交通部门有合作,目的是为了获取城市街道的实时状态。

每一天都会有一些街道因为维修或者施工而关闭,所以为了节约时间不走冤枉路,消防员需要选择一条不经过关闭的街道的路线到达火灾发生地。

该城市被划分为不重叠的火区, 每个火区由一个消防站负责。

当火灾发生接到报警时,中心调度员MM会发送警报到管辖该区域的消防站, 并且提供多条从消防站到火灾发生地的路线供选择。

你想追调度员MM, 所以你决定编写一个程序帮助中心调度员MM生成从消防站到灾区的路线。

该城市的每个火区都有一张单独的地图。

地图上的街道路口(Streetcorner)被标志为一个不超过21的整数(每张地图的街道路口数量不超过21), 并且每张地图的消防站

的编号都是1(on corner #1).

分析与总结:

一看到这题,看到过题率这么低以为很难,但是看到完题目觉得挺容易,很快就写好了,提交后却TLE了。。。

在此TLE。。。

又一次TLE。。。

于是问了谷哥, 学到了一样新东西。

之所以会超时,原因在于可能会有很多条路是完全到达不了目标的,比如,南京到北京,需要往北边走,但是路是非常多的,

除了往北边的路,还有往南边,西边,东边的路,而走这些方向走无疑是南辕北辙的, 走到死也到不了北京,就算绕地球一圈

到达终点,但是黄花菜早就已经凉了(调度员MM还等着你呢~~)。而超时的原因就出在了这里。

所以, 从起点开始搜索之前,很有必要先确定一下有那些路是可以到达目标的。

如何确定那些路可以到目标呢? 我们只需要先从目标点开始进行搜索,把所有搜索到得路径都进行标记。

然后,再从起点处进行搜索,在搜索之前,要先判断一下这个路径是否有被之前标记过,如果没有被标记,那么说明它是不可能

走到目标处的。这样的话,就不会盲目地去走了,也大大提高了效率。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 22
using namespace std;
int G[MAXN][MAXN], route[MAXN], edge[MAXN], cnt, end, numRoute;
bool vis[MAXN], used[MAXN], occur[MAXN];  

void search(int cur, int u){
    if(u == end){
        ++numRoute;
        printf("%d", route[0]);
        for(int i=1; i<cur; ++i)
            printf(" %d", route[i]);
        printf("\n");
        return;
    }
    int v;
    for(int i=1; i<cnt; ++i)if(used[edge[i]]){// 回溯时判断这条路经是否可以到达终点
        int v=edge[i];
        if(G[u][v] && !vis[v]){
            vis[v] = true;
            route[cur] = v;
            search(cur+1, v);
            vis[v] = false;
        }
    }
}  

int que[10000];
// bfs预处理, 用dfs也可
void bfs(int u){
    int front=0, rear=0;
    que[rear++] = u;
    while(front < rear){
        int t = que[front++];
        for(int i=0; i<cnt; ++i)if(!used[edge[i]] && G[t][edge[i]]){
            used[edge[i]] = true; //经过的标志为true
            que[rear++] = edge[i];
        }
    }
}  

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    int u,v,cas=1;  

    while(scanf("%d", &end) != EOF){  

        memset(G, 0, sizeof(G));
        memset(occur, 0, sizeof(occur));
        while(scanf("%d %d", &u, &v)!=EOF){
            if(!u && !v) break;
            occur[u] = occur[v] = true;
            ++G[u][v];
            ++G[v][u];
        }
        cnt = 0;
        for(int i=1; i<MAXN; ++i)if(occur[i]){
            edge[cnt++] = i;
        }  

        memset(vis, 0, sizeof(vis));
        memset(used, 0, sizeof(used));
        vis[end] = true;
        used[end] = true;
        bfs(end);  

        printf("CASE %d:\n", cas++);
        memset(vis, 0, sizeof(vis));  

        route[0] = 1;
        vis[1] = true;
        numRoute = 0;
        search(1, 1);
        printf("There are %d routes from the firestation to streetcorner %d.\n", numRoute, end);
    }
    return 0;
}

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索搜索
, firing the topic
, of
The
uva oj、uva和uvb的区别、uvb、uva大学、弗吉尼亚大学,以便于您获取更多的相关知识。

时间: 2024-12-23 18:38:38

UVa 208:Firetruck,双向搜索进行剪枝的相关文章

UVa 140 Bandwidth:枚举全排列&amp;amp;剪枝搜索

140 - Bandwidth Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=76 Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and anord

UVa 993:Product of digits

[链接] http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=934 [原题] For a given non-negative integer number N , find the minimal natural Q such that the product of all digits of Q is eq

UVa 301:Transportation

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=237 题目类型: 回溯法 原题: Ruratania is just entering capitalism and is establishing new enterprising activities in many fields includ

UVa 272 TEX Quotes (water ver.)

272 - TEX Quotes Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=208 TeX is a typesetting language developed by Donald Knuth. It takes source text togethe

poj 2248--Addition Chains (uva 529--Addition Chains)

点击打开链接 题目意思:   给定一个正数 n ,要求找到一个最短序列满足 一下4个条件        1 a0 = 1          2 am = n          3 a0 < a1 < a2 < ... < am-1 < am           4 For each k (1<=k<=m) there exist two (not necessarily different) integers i    and j (0<=i, j<=

uva 10317 Equating Equations

点击打开链接uva 10317 思路:搜索 分析: 1 给定一个等式判断两边是否相等,如果一个等式相等那么通过移项到同一边可以得到正数的和等于负数 2 那么通过分析1我们可以知道我们可以求出这个等式的所有数字的和,判断和是否为偶数.如果和为奇数那么肯定不可能成立,因为不能被平分 3 通过分析2的剪枝之后,那么可以知道题目说了最多有16 个数字.那么我们就搜索这个2^16种状态,找到一个满足的即可.注意在搜索的过程中可以进行剪枝 代码: #include<cstdio> #include<

uva 10422 - Knights in FEN ID+dfs

10422 - Knights in FEN        经典的棋盘类问题,移动骑士到达指定状态,最少要几次,如果超过10次则输出Unsolvable in less than 11 move(s).        一开始想bfs的,但是状态量比较大,又懒得写hash,又想到了最坏情况,也就是超出10次时,dfs和bfs复杂度都一样,于是就果断用了ID+dfs,编程难度非常低.      不用加剪枝就可以过了,我的代码里加了个最优下限,这样不用每次从0开始进行ID,刚有想到可以利用当前最优情况

UVa 10602

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543 类型:贪心 原题: Company Macrohard has released it's new version of editor Nottoobad, which can understand a few voice commands.

UVa 10392 Factoring Large Numbers:素因子分解

10392 - Factoring Large Numbers Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=100&page=show_problem&problem=1333 One of the central ideas behind much cryptography is that factoring