本文共 2238 字，大约阅读时间需要 7 分钟。
//// main.cpp// dfs-bfs搜索//// Created by liuzhe on 16/8/10.// Copyright © 2016年 my_code. All rights reserved.//#include#include #include #include #include using namespace std;char map[20][20]; //记录地图int vis[20][20]; //访问标记int dir[4][2] = {0,1,0,-1,1,0,-1,0}; //四个方向int n; //行和列int ans; //记录走过的字母个数struct state{ int x,y; //记录坐标 int count; //记录步数 char c; //字符}sta[600];int res = 0; //记录最后的答案int check(state s, char c){ if ( vis[s.x][s.y] == 0 && s.x >= 0 &&s.x < n && s.y >= 0 && s.y < n && (s.c =='.'||(s.c <= c && s.c >= 'A' && s.c <= 'Z'))) //判断可以不可以走 { return 1; } else { return 0; }}void bfs(state s,char c) //bfs算法{ queue q; //定义队列 state now,next; //现在的 和下一个 s.count = 0; //初始化步数 q.push(s); //入队 vis[s.x][s.y] = 1; while (!q.empty()) { now = q.front(); //队首元素 q.pop(); //出队 if (now.c == c ) //如果走到目标字母 { ans++; res += now.count; //结果加上走的步数 map[now.x][now.y] = '.'; //然后走过的字母变为'.' now.count = 0; next.count = 0; memset(vis,0,sizeof(vis)); //初始化走过的路 return ; } for ( int i = 0 ; i < 4 ;i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; next.count = now.count + 1; //四个方向 next.c = map[next.x][next.y]; if (check(next , c)) { q.push(next); //如果符合条件，入队 vis[next.x][next.y] = 1; //访问过了 不再访问 } } } return; //如果无路可走 退出}int main(){ int t; scanf("%d",&t); int temp[26]; for (int cas = 1 ; cas <= t ; cas ++ ) { memset(vis,0,sizeof(vis)); res = 0; ans = 1; scanf("%d",&n); getchar(); int k = 0; int l = 0; for (int i = 0 ; i < n ; i++ ) { for ( int j = 0 ; j < n ; j++ ) { scanf("%c",&sta[l].c); map[i][j] = sta[l].c; //结构数组的字符 sta[l].x = i; sta[l].y = j; if (sta[l].c >= 'A' && sta[l].c <= 'Z') { temp[sta[l].c-'A'] = l; k++; //字母总个数 } l++; //结构数组的下标 } getchar(); } for (int i = 1 ; i < k ; i++ ) { //printf("%c\n",sta[temp[i-1]].c); bfs(sta[temp[i-1]],('A' + i)); //记录A 到B的路径 然后再B到C 的路径，直到最后一个 if ( ans < i ) break; } if (ans == k && k > 0) //如果字母全部走过了 { printf("Case %d: %d\n",cas, res); } else { printf("Case %d: Impossible\n",cas); //没有走遍所有的字母 } if ( cas != t) getchar(); } return 0;}
转载地址：http://inali.baihongyu.com/