主要还是剪枝。这里的剪枝就是对下一个搜索的数字进行预处理，如果往这个方向能搜到的数字长度大于ans或者可能的最大数字大于ans就继续，不然就剪枝。 这里的预处理精度不需要很高，就很普通的bfs就行了，即便最大情况可能取不到（或者说，基本上不可能取到）。因为总的数字并不是太多，简单的剪枝足够了。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<map> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 16; const int xx[] = {-1,0,1,0}; const int yy[] = {0,-1,0,1}; string ans,ss; char a[maxn][maxn]; bool vis[maxn][maxn]; int n,m; int pre(int x,int y){//预处理 queue<pair<int,int>> Q; bool vis2[maxn][maxn] = {}; Q.push({x,y}); ss = ""; vis2[x][y] = 1; while(!Q.empty()){ int i = Q.front().first,j = Q.front().second;Q.pop(); ss+=a[i][j]; for(int k = 0;k < 4;++k){ int nx = i + xx[k],ny = j + yy[k]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == '#' || vis[nx][ny] || vis2[nx][ny]) continue; vis2[nx][ny] = 1; Q.push({nx,ny}); } } sort(ss.begin(),ss.end()); reverse(ss.begin(),ss.end()); return (int)ss.size(); }//ss存放可能组成的数字，即使它可能不能被取到 void dfs(int x,int y,string s){ s += a[x][y]; vis[x][y] = 1; if (s.length() > ans.length() || (s.length() == ans.length() && s > ans)) ans = s; for(int k = 0;k < 4;++k){ int nx = x + xx[k],ny = y + yy[k]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == '#' || vis[nx][ny]) continue; int maxl = pre(nx,ny); if (s.length() + maxl > ans.length() || (s.length() + maxl == ans.length() && s + ss > ans)) {//长度更大或者可能组成的数更大 dfs(nx,ny,s); } } vis[x][y] = 0; } int main(){ while(cin >> n >> m && n && m){ for(int i = 0;i < n;++i) for(int j = 0;j < m;++j) cin >> a[i][j]; memset(vis,0,sizeof vis); ans = ""; for(int i = 0;i < n;++i) for(int j = 0;j < m;++j) if (a[i][j] != '#') dfs(i,j,""); cout << ans << endl; } }