首页 > 代码库 > HNU 12894 Keys dfs

HNU 12894 Keys dfs

2024-07-17 02:12:26   221人阅读

题意：给你一个N×M的简单图，其中有门，墙，通道，和文件，打开每扇门必须要有某一把特定的钥匙，问你最多能拿到几个文件

解题思路：深度优先，每一次走一个格子将它标记以后都不走，遇到门以后如果有钥匙，将门打开，如果没有，將门加入队列，搜完以后，遍历没有打开的门看是否已经有钥匙了，如果有 从门开始dfs，直到没有可以打开的门

解题代码：

  1 // File Name: k.cpp  2 // Author: darkdream  3 // Created Time: 2014年08月10日 星期日 16时31分20秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25  26 using namespace std; 27 int t;  28 int n,m; 29 int hs[30]; 30 int nv[30]; 31 char str[200][200]; 32 struct node{ 33     int x, y ;  34 }site[30][10000]; 35 int nums[30]; 36 int xadd[] = {1,-1,0,0}; 37 int yadd[] = {0,0,-1,1}; 38 int visit[200][200]; 39 int sum = 0; 40 void dfs(int x , int y) 41 { 42     //printf("%d %d %c\n",x,y,str[x][y]); 43     for(int i = 0  ;i <= 3;i ++) 44     { 45         int tx = x + xadd[i]; 46         int ty = y + yadd[i]; 47         if(!visit[tx][ty]) 48         { 49             if(str[tx][ty] ==‘$‘)  50             { 51                 sum ++ ; 52                 visit[tx][ty] = 1; 53                 dfs(tx,ty); 54             } 55             else if(str[tx][ty]  == ‘.‘) 56             { 57                 visit[tx][ty] = 1;  58                 dfs(tx,ty); 59             }else if(str[tx][ty] <= ‘z‘ && str[tx][ty]>= ‘a‘) 60             { 61             //    printf("%c\n",str[tx][ty]); 62                 hs[str[tx][ty] - ‘a‘] = 1;  63                 visit[tx][ty] =1 ;  64                 dfs(tx,ty); 65             }else if(str[tx][ty] <= ‘Z‘ && str[tx][ty] >= ‘A‘) 66             { 67             //    printf("%d %d %c\n",tx,ty,str[tx][ty]); 68                 if(hs[str[tx][ty] - ‘A‘]) 69                 { 70                     visit[tx][ty] = 1;  71                     dfs(tx,ty); 72                 }else{ 73                     nv[str[tx][ty] - ‘A‘] ++;  74                     site[str[tx][ty] - ‘A‘][nv[str[tx][ty]-‘A‘]].x = tx;  75                     site[str[tx][ty] - ‘A‘][nv[str[tx][ty]-‘A‘]].y = ty;  76                 } 77             } 78         } 79     } 80 } 81 int main(){ 82     scanf("%d",&t); 83     while(t--) 84     { 85         memset(visit,0,sizeof(visit)); 86         sum = 0 ;  87         memset(str,0,sizeof(str)); 88         memset(hs,0,sizeof(hs)); 89         memset(nv,0,sizeof(nv)); 90         scanf("%d %d",&n,&m);  91         for(int i = 1;i <= n;i ++) 92         { 93             scanf("%s",&str[i+1][2]); 94         } 95         char temp[200] ;  96         scanf("%s",temp); 97         int ltemp = strlen(temp); 98         if(temp[0] != ‘0‘) 99             for(int i = 0 ;i < ltemp ;i ++)100             {101                 hs[temp[i] - ‘a‘] = 1; 102             }103         for(int i = 1;i <= n + 2 ; i++)104             str[i][1] = str[i][m+2] = ‘.‘;105         for(int i = 1;i <= m + 2 ;i ++ )106             str[1][i] = str[n+2][i] = ‘.‘;107         visit[1][1] = 1 ; 108         dfs(1,1);109         int ok  = 0 ; 110         do{111             ok = 0 ; 112             for(int i = 0 ;i <= 26;i ++)113             {114                 if(hs[i] && nv[i])115                 {116                     //printf("%d\n",i);117                     ok = 1;118                     visit[site[i][nv[i]].x][site[i][nv[i]].y] = 1; 119                     dfs(site[i][nv[i]].x,site[i][nv[i]].y);120                     nv[i]--;121                 }122             }123         }while(ok);124         printf("%d\n",sum);125     }126     return 0;127 }
View Code

 


联系
我们