博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 208 Firetruck
阅读量:5237 次
发布时间:2019-06-14

本文共 3926 字,大约阅读时间需要 13 分钟。

 

 Firetruck 

 

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 #1CASE #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.

 

Sample Input

 

61 21 33 43 54 65 62 32 40 042 33 45 11 67 88 92 55 73 11 84 66 90 0

 

Sample Output

 

CASE 1:1 2 3 4 61 2 3 5 61 2 4 3 5 61 2 4 61 3 2 4 61 3 4 61 3 5 6There are 7 routes from the firestation to streetcorner 6.CASE 2:1 3 2 5 7 8 9 6 41 3 41 5 2 3 41 5 7 8 9 6 41 6 41 6 9 8 7 5 2 3 41 8 7 5 2 3 41 8 9 6 4There are 8 routes from the firestation to streetcorner 4.

 

题意:最多21个点。。给定一个终点。和一些连接方式,要求输出1到终点的所有路径。

思路:深搜回溯。。。超时了。。要多加一个优化。把从终点开始有与终点相连的点全部拿出来,在这些点的基础上进行深搜回溯。。(估计数据中。有数据是起点周围是稠密图,却连不到终点的那种)

 

#include 
#include
int end;int x, y;int map[25][25];int vis[25];int save[25];int out[25];int num;int max;void find(int dian){ save[dian] = 1; for (int i = 1; i <= max; i ++) { if (map[dian][i] == 1 && save[i] == 0) { find(i); } }}void dfs(int dian, int nn){ out[nn] = dian; if (dian == end) { num ++; int bo = 0; for (int i = 0; i <= nn; i ++) { if (bo == 0) { bo = 1; printf("%d", out[i]); } else { printf(" %d", out[i]); } } printf("\n"); return; } for (int i = 1; i <= max; i ++) { if (save[i] == 0) continue; if (map[dian][i] == 1 && vis[i] == 0) { vis[i] = 1; dfs(i, nn + 1); vis[i] = 0; } }}int main(){ int t = 1; while (scanf("%d", &end) != EOF) { num = 0; max = 0; memset(save, 0, sizeof(save)); memset(vis, 0, sizeof(vis)); vis[1] = 1; memset(map, 0, sizeof(map)); while (scanf("%d%d", &x, &y) != EOF && x + y) { map[x][y] = map[y][x] = 1; if (max < x) max = x; if (max < y) max = y; } printf("CASE %d:\n", t ++); find(end); memset(vis, 0, sizeof(vis)); vis[1] = 1; dfs(1, 0); printf("There are %d routes from the firestation to streetcorner %d.\n", num, end); } return 0;}

 

 

转载于:https://www.cnblogs.com/pangblog/p/3238905.html

你可能感兴趣的文章
win10 uwp 使用 msbuild 命令行编译 UWP 程序
查看>>
解剖SQLSERVER 第十四篇 Vardecimals 存储格式揭秘(译)
查看>>
Chapter 1 Securing Your Server and Network(2):管理服务的SIDs
查看>>
2000条你应知的WPF小姿势 基础篇<51-56 依赖属性>
查看>>
[Head First设计模式]一个人的平安夜——单例模式
查看>>
SQL Server 大数据搬迁之文件组备份还原实战
查看>>
HTML5实现图片文件异步上传
查看>>
Eclipse 4.2 汉化
查看>>
Zerver是一个C#开发的Nginx+PHP+Mysql+memcached+redis绿色集成开发环境
查看>>
网络时间获取
查看>>
多线程实现资源共享的问题学习与总结
查看>>
Code as IaaS for Azure : Terraform 初步
查看>>
WebFrom 小程序【分页功能 】
查看>>
Learning-Python【26】:反射及内置方法
查看>>
day7--面向对象进阶(内含反射和item系列)
查看>>
Python深入01 特殊方法与多范式
查看>>
torch教程[1]用numpy实现三层全连接神经网络
查看>>
java实现哈弗曼树
查看>>
转:Web 测试的创作与调试技术
查看>>
转:apache 的mod-status
查看>>