//给一个n*m的图//.表示空白地//*表示有黄金//#表示墙//一个人需要按照A…Z..a..z的顺序以最短路径走到下一个//每次只能在他的路线上经过的地方取一块黄金//问最多能取多少黄金//对于每次起点和终点,用bfs搜索最短路，，再用dfs找出最短路线经过的所有点//对于第i次找最短路线与其走过的点建立边，然后用二分匹配就能找出#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<queue>using namespace std ;const int maxn = 110 ;vector<int> vec[maxn] ;int match[maxn*maxn] ;int vis[maxn][maxn] ;int visit[maxn*maxn] ;char map[maxn][maxn] ;int pos[maxn*maxn] ;int len ;int st_x , st_y , en_x, en_y ;int dx[4] = {0 , 1 , 0 , -1} ;int dy[4] = {1 , 0 , -1 , 0} ;int n , m ;queue<int> que ;int sum = 0 ;void dfs(int x , int y , int num){sum++ ;if(x == st_x && y == st_y)return ;if(map[x][y] == '*')vec[num].push_back(x*m+y) ;for(int i = 0;i < 4;i++){int nx = x + dx[i] ;int ny = y + dy[i] ;if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] + 1 != vis[x][y])continue ;dfs(nx , ny ,num);}vis[x][y] = 0 ;}int bfs(int num){while(que.size())que.pop() ;memset(vis, 0 ,sizeof(vis)) ;que.push(st_x) ;que.push(st_y) ;vis[st_x][st_y] = 1;while(que.size()){int x = que.front() ; que.pop() ;int y = que.front() ; que.pop() ;if(x == en_x && y == en_y){dfs(x , y ,num) ;return true ;}int step = vis[x][y] ;for(int i = 0;i < 4;i++){int nx = dx[i] + x ;int ny = dy[i] + y ;if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || map[nx][ny] == '#')continue ;vis[nx][ny] = vis[x][y] + 1 ;que.push(nx);que.push(ny) ;}} return false ;}int find(int u){for(int i = 0;i < vec[u].size() ;i++){int v = vec[u][i] ;if(!visit[v]){visit[v] = 1 ;if(match[v] == -1 || find(match[v])){match[v] = u ;return true ;}}}return false ;}int Match(){int ans = 0 ;memset(match , -1 , sizeof(match)) ;for(int i = 0;i < len – 1;i++){memset(visit ,0 , sizeof(visit)) ;if(find(i))ans++ ;}return ans ;}int main(){//freopen("in.txt" ,"r" , stdin) ;while(~scanf("%d%d" ,&n , &m)){memset(pos ,0 , sizeof(pos)) ;len = 0 ;for(int i = 0;i < n;i++){scanf("%s" , &map[i]) ;for(int j = 0;j < m;j++)if((map[i][j] >= 'a'&&map[i][j] <='z'))pos[map[i][j]-'a'+26] = i*m + j +1,len++ ;else if(map[i][j] >= 'A' && map[i][j] <= 'Z')pos[map[i][j]-'A'] = i*m + j + 1, len++ ;}int flag = 0 ;for(int i = 0;i < len;i++){if(!pos[i])flag = 1 ;pos[i]–;}if(len < 2 || flag){puts("-1");continue ;}for(int i = 0;i < len – 1;i++){vec[i].clear() ;st_x = pos[i]/m;st_y = pos[i]%m;en_x = pos[i+1]/m;en_y = pos[i+1]%m ;if(!bfs(i)){flag = 1;break ;}}if(flag)puts("-1") ;elseprintf("%d\n" , Match()) ;}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，
