F

题目大意：有一个R*C的矩阵，矩阵里面有1~9的数字（太好了不用处理前导0），或者是#（代表不能通过），先要从矩阵任意一点出发（之前英语抓鸡看成了边界，英语差的孩纸伤不起啊>_<），只能往上下左右四个方向移动，每个格子不能重复走，到达矩阵内任意一点。把这条路径的数字连起来变成一个很大的数字，求这个数字最大是什么。
思路：DP？记忆化搜索？30个点噢，时间吃得消内存都吃不消啦。所以呢？搜索。还是超时啊？剪枝啊。
剪枝1：假设当前答案为ans，那么当我们走到一个点(x, y)的时候，作一个小小的搜索预判。假设现在能从(x, y)走到的点，我们都能到达，这是最好的情况。设从(x, y)能走到的点数为maxlen，那么如果从出发点走到(x, y)经过的格子，加上maxlen，都没有ans的长度大，那么不管从(x, y)怎么搜，我们都不能取代我们现在的ans（长才是王道懂不懂），那么直接回溯，不要这个点了。这个剪枝效力还是不错的，但是还是TLE，我试过了 QAQ。最近有点脑残，明明可以做一个数据测试一下非要交上去试一下……
剪枝2：同剪枝1，假设当前答案为ans，那么当我们走到一个点(x, y)的时候，搜到maxlen（同剪枝1），如果从出发点走到(x, y)经过的格子，加上maxlen，大于ans的长度，我们就只能继续搜了……如果等于呢？那么就再作一个最好预期的答案。把从(x, y)能走到的所有格子，从大到小排好序（我的代码是从小到大排序然后从后面开始取的……），都接在当前走到(x, y)的后面，这是从(x, y)可能搜到的最好的答案，如果这个都比ans要小，那么我们也就没有必要往下搜了，果断回溯。
PS：弄个结构体存答案很好写妥妥的。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 const int MAXN = 33;
10 
11 struct Node {
12     int a[MAXN], len;
13     void clear() {
14         len = 0;
15     }
16     void print() {
17         //cout<<len<<endl;
18         for(int i = 0; i < len; ++i) printf("%d", a[i]);
19         printf("
");
20     }
21     bool operator < (const Node &rhs) const {
22         if(len != rhs.len) return len < rhs.len;
23         for(int i = 0; i < len; ++i)
24             if(a[i] != rhs.a[i]) return a[i] < rhs.a[i];
25         return false;
26     }
27 };
28 
29 int fx[] = {1, 0, -1, 0};
30 int fy[] = {0, 1, 0, -1};
31 
32 Node ans, now, tmp;
33 char mat[MAXN][MAXN];
34 bool vis[MAXN][MAXN];
35 bool vis2[MAXN][MAXN];
36 int n, m;
37 int can[MAXN];
38 
39 int maxlen(int x, int y) {
40     queue<int> que; que.push(x * MAXN + y);
41     int ret = 1;
42     can[0] = mat[x][y] - '0';
43     memset(vis2, 0, sizeof(vis2));
44     vis2[x][y] = 1;
45     while(!que.empty()) {
46         int tmp = que.front(); que.pop();
47         int nx = tmp / MAXN, ny = tmp % MAXN;
48         for(int i = 0; i < 4; ++i) {
49             int px = nx + fx[i], py = ny + fy[i];
50             if(!isdigit(mat[px][py]) || vis[px][py] || vis2[px][py]) continue;
51             vis2[px][py] = true;
52             can[ret++] = mat[px][py] - '0';
53             que.push(px * MAXN + py);
54         }
55     }
56     return ret;
57 }
58 
59 void dfs(int x, int y) {
60     now.a[now.len++] = mat[x][y] - '0';
61     vis[x][y] = true;
62     for(int i = 0; i < 4; ++i) {
63         int px = x + fx[i], py = y + fy[i];
64         if(!isdigit(mat[px][py]) || vis[px][py]) continue;
65         int wantlen = maxlen(px, py);
66         if(now.len + wantlen < ans.len) continue;
67         if(now.len + wantlen == ans.len) {
68             sort(can, can + wantlen);
69             tmp = now;
70             for(int i = wantlen - 1; i >= 0; --i) tmp.a[tmp.len++] = can[i];
71             if(tmp < ans) continue;
72         }
73         dfs(px, py);
74     }
75     if(ans < now) ans = now;
76     --now.len;
77     vis[x][y] = false;
78 }
79 
80 int main() {
81     while(scanf("%d%d", &n, &m) != EOF) {
82         if(n + m == 0) break;
83         memset(mat, 0, sizeof(mat));
84         for(int i = 1; i <= n; ++i) scanf("%s", &mat[i][1]);
85         ans.clear(); now.clear();
86         for(int i = 1; i <= n; ++i) {
87             for(int j = 1; j <= m; ++j)
88                 if(isdigit(mat[i][j])) dfs(i, j);
89         }
90         ans.print();
91     }
92 }