网上很多人都是用的DFS加上BFS判断后续结点最大数量然后用来剪枝， 我只是用了DFS就过了~
其实方法很简单，受到了例题 “万圣节后的早晨” 一题的启发，其实矩阵中有很多无用的障碍格，所以在搜索的时候就会多出很多无用的判断 。 因此我们不妨将有用的格子提出来再建一张图，然后DFS，如果只是这样发现会超时，其实对于一个样例来说最浪费时间的情况是：当前答案的长度为所有格子数时，不可能有其他更长的了，所以如果将要枚举的情况的第一个数比当前答案的第一个数小，那么就不必枚举这个情况了，直接省下了一个超长的递归 。
加上这个小小的优化就可以通过了，时间跑的比BFS优化的还快。。。
其实还可以优化很多，，如果用上BFS判断应给会更快 。
细节参见代码：
#include<bits/stdc++.h>using namespace std;int T,n,m,vis[35],cnt,vis2[16][16];char a[35],ans[35],ans_len;int dx[] = {0,1,0,-1};int dy[] = {1,0,-1,0};char s[16][16],ss[35];vector<int> g[35];void dfs(int cur,int len) {bool ok = false;for(int i=0;i<g[cur].size();i++) {int v = g[cur][i];if(!vis[v]) {ok = true;vis[v] = 1;a[len] = ss[v];dfs(v,len+1);vis[v] = 0;}}if(ok) return ; //如果该层没有进行递归，说明已经到了尽头，更新答案。a[len] = '\0';if(len > ans_len) {ans_len = len;memcpy(ans,a,sizeof(a));}else if(len == ans_len) {if(memcmp(a,ans,sizeof(a)) > 0)memcpy(ans,a,sizeof(a));}return ;}int main() {while(~scanf("%d%d",&n,&m)) {if(!n && !m) return 0;for(int i=1;i<=n;i++) scanf("%s",s[i]+1);int x[35],y[35],id[16][16]; cnt = 0;for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(s[i][j] != '#') {x[cnt] = i; y[cnt] = j; ss[cnt] = s[i][j]; id[i][j] = cnt++; //ss[]数组为新图中对应结点的值}}}for(int i=0;i<cnt;i++) g[i].clear(); //建新图for(int i=0;i<cnt;i++) {for(int j=0;j<4;j++) {int r = x[i]+dx[j];int c = y[i]+dy[j];if(r<1||r>n||c<1||c>m) continue;if(s[r][c]!='#') {g[i].push_back(id[r][c]);}}}ans_len = 0;memset(vis,0,sizeof(vis));for(int i=0;i<cnt;i++) {if(ans_len == cnt && ss[i] < ans[0]) continue ; //小剪枝vis[i] = 1;a[0] = ss[i];dfs(i,1);vis[i] = 0;}printf("%s\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
当一个人真正觉悟的一刻，他放弃追寻外在世界的财富，
