13杭州现场赛Stealing Harry Potter's Precious(bfs+dfs)

题意:一个简单图,给你一个起点,图中最多有4个宝藏,问你收集这四个宝藏最多要多少步.
解题思路:很简单的一个题,因为宝藏比较少,所以先对宝藏进行一个全排,然后再一步一步算步数.
解题代码:
  1 // File Name: d.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年05月06日 星期二 19时03分57秒
  4 
  5 #include<vector>
  6 #include<set>
  7 #include<deque>
  8 #include<stack>
  9 #include<bitset>
 10 #include<algorithm>
 11 #include<functional>
 12 #include<numeric>
 13 #include<utility>
 14 #include<sstream>
 15 #include<iostream>
 16 #include<iomanip>
 17 #include<cstdio>
 18 #include<cmath>
 19 #include<cstdlib>
 20 #include<cstring>
 21 #include<ctime>
 22 
 23 using namespace std;
 24 int n , m;
 25 struct node{
 26   int x, y ,s;
 27 }LIST[10005];
 28 int visit[104][104];
 29 int MAP[104][104];
 30 struct node1{
 31   int x, y ; 
 32 }a[10];
 33 int xadd[] = {0,0,1,-1};
 34 int yadd[] = {1,-1,0,0};
 35 int ok = 1;
 36 int bfs(int bx, int by ,int ex,int ey)
 37 {
 38     //printf("%d %d %d %d
",bx,by,ex,ey);
 39     LIST[1].x = bx ; 
 40     LIST[1].y = by ; 
 41     LIST[1].s = 0 ; 
 42     int l = 1, r= 1; 
 43     int tempok = 0 ;
 44     memset(visit,0,sizeof(visit));
 45     visit[bx][by] = 1; 
 46     while(l <= r )
 47     {
 48       //  printf("%d %d
",LIST[l].x,LIST[l].y);
 49         if(LIST[l].x == ex && LIST[l].y == ey)
 50         {
 51           tempok = 1; 
 52           break;
 53         }
 54         for(int i = 0 ; i <= 3;i ++)
 55         {
 56           int tempx = LIST[l].x + xadd[i];
 57           int tempy = LIST[l].y + yadd[i];
 58           if(!visit[tempx][tempy] && MAP[tempx][tempy])
 59           {
 60              visit[tempx][tempy] = 1;
 61              r ++ ;
 62              LIST[r].x = tempx; 
 63              LIST[r].y = tempy; 
 64              LIST[r].s = LIST[l].s +1 ; 
 65           }
 66         }
 67        l ++;
 68     }
 69     if(tempok == 0)
 70         ok = 0;
 71     else return LIST[l].s;
 72 
 73 }
 74 int main(){
 75 
 76 
 77       while(scanf("%d %d",&n,&m) != EOF)
 78       {
 79         if(n == 0  && m == 0)
 80             break;
 81         memset(MAP,0,sizeof(MAP));
 82         memset(a,0,sizeof(a));
 83         for(int i = 1;i <= n;i ++)
 84         {
 85           char str[104];
 86           scanf("%s",&str[1]);
 87           for(int j = 1;j <= m;j ++)
 88           {
 89              if(str[j] == '#')
 90              {
 91              }
 92              else 
 93              {
 94                  MAP[i][j] = 1;
 95                  if(str[j] == '@')
 96                  {
 97                  a[0].x = i ; 
 98                  a[0].y = j; 
 99                  }
100              }
101           }
102         }
103         int  k ; 
104         scanf("%d",&k);
105         for(int i = 1;i <= k;i ++)
106             scanf("%d %d",&a[i].x,&a[i].y);
107         int temp[6];
108         for(int i =0 ;i < k;i ++)
109           temp[i] = i + 1; 
110         ok = 1; 
111         int min = 1000000;
112         do{
113            int last = 0;
114            int sum = 0 ; 
115            for(int i = 0 ;i < k ;i ++)
116            {
117              sum +=  bfs(a[last].x,a[last].y,a[temp[i]].x,a[temp[i]].y); 
118              last = temp[i];
119            }
120            if (sum <= min)
121                min = sum;
122         
123           //  printf("%d
",sum);
124         }while(next_permutation(temp,temp+k));    
125         if(ok == 0 )
126             printf("-1
");
127         else 
128         printf("%d
",min);
129       }
130       
131 return 0 ;
132 }
View Code
没有梦想，何谈远方