首页 > ACM题库 > HDU-杭电 > HDU 1307 N-Credible Mazes-DFS-[解题报告] C++
2013
12-04

HDU 1307 N-Credible Mazes-DFS-[解题报告] C++

N-Credible Mazes

问题描述 :

An n-tersection is defined as a location in n-dimensional space, n being a positive integer, having all non-negative integer coordinates. For example, the location (1,2,3) represents an n-tersection in three dimensional space. Two n-tersections are said to be adjacent if they have the same number of dimensions and their coordinates differ by exactly 1 in a single dimension only. For example, (1,2,3) is adjacent to (0,2,3) and (2,2,3) and (1,2,4), but not to (2,3,3) or (3,2,3) or (1,2). An n-teresting space is defined as a collection of paths between adjacent n-tersections.

Finally, an n-credible maze is defined as an n-teresting space combined with two specific n-tersections in that space, one of which is identified as the starting n-tersection and the other as the ending n-tersection.

输入:

The input file will consist of the descriptions of one or more n-credible mazes. The first line of the description will specify n, the dimension of the n-teresting space. (For this problem, n will not exceed 10, and all coordinate values will be less than 10.) The next line will contain 2n non-negative integers, the first n of which describe the starting n-tersection, least dimension first, and the next n of which describe the ending n-tersection. Next will be a nonnegative number of lines containing 2n non-negative integers each, identifying paths between adjacent n-tersections in the n-teresting space. The list is terminated by a line containing only the value ?. Several such maze descriptions may be present in the file. The end of the input is signalled by space dimension of zero. No further data will follow this terminating zero.

输出:

For each maze output it’s position in the input; e.g. the first maze is "Maze #1", the second is "Maze #2", etc. If it is possible to travel through the n-credible maze’s n-teresting space from the starting n-tersection to the ending n-tersection, also output "can be travelled" on the same line. If such travel is not possible, output "cannot be travelled" instead.

样例输入:

2 
0 0 2 2
0 0 0 1
0 1 0 2
0 2 1 2
1 2 2 2
-1
3
1 1 1 1 2 3
1 1 2 1 1 3
1 1 3 1 2 3
1 1 1 1 1 0
1 1 0 1 0 0
1 0 0 0 0 0
-1
0

样例输出:

Maze #1 can be travelled
Maze #2 cannot be travelled 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1307

先说一下题意,就是给你n维起始点和终点的坐标,然后后面给出一系列的点,每一行表示这两个点之间有通路,最后让你判断一下能否从起点出发走到终点。

由于最多不超过10维,那么我们把每个点的坐标转化为一个整数,然后建邻接表,这样dfs就可以了(值得注意的是我们用set来判重,当然你也可以用数组什么的)

可以说是dfs+map+set的妙用了!

#include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<vector>
 #include<set>
 #include<map>
 using namespace std;
 int st,ed;
 map<int,vector<int> >Map;
 set<int>Set;
 int n;
 bool Input(int &num,int n){
     num=0;
     int x;
     for(int i=1;i<=n;i++){
         scanf("%d",&x);
         if(x==-1)return false;
         num=num*10+x;
     }
     return true;
 }
 
 bool dfs(int st,int ed){
     if(st==ed)return true;
     for(int i=0;i<Map[st].size();i++){
         int v=Map[st][i];
         //只能返回0或1,1表示该数已经插入
         if(!Set.count(v)){
             Set.insert(v);
             if(dfs(v,ed))return true;
         }
     }
     return false;
 }
 
 
 int main(){
     int x,t=1;
     while(scanf("%d",&n),n){
         Map.clear(),Set.clear();
         Input(st,n);
         Input(ed,n);
         int s,e;
         while(Input(s,n)){
             Input(e,n);
             Map[s].push_back(e);
             Map[e].push_back(s);
         }
         if(dfs(st,ed)){
             printf("Maze #%d can be travelled\n",t++);
         }else 
             printf("Maze #%d cannot be travelled\n",t++);
     }
     return 0;
 }

 


,
  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.