Description

You have a maze with obstacles and non-zero digits in it:

You can start from any square, walk in the maze, and finally stop at some square. Each step, you may only walk into one of the four neighbouring squares (up, down, left, right) and you cannot walk into obstacles or walk into a square more than once. When you finish, you can get a number by writing down the digits you encounter in the same order as you meet them. For example, you can get numbers 9784, 4832145, etc. The biggest number you can get is 791452384, shown in the picture above.

Your task is to find the biggest number you can get.

Input

There will be at most 25 test cases. Each test begins with two integers RR and CC (2≤R,C≤152≤R,C≤15, R∗C≤30R∗C≤30), the number of rows and columns of the maze. The next RR rows represent the maze. Each line contains exactly CC characters (without leading or trailing spaces), each of them will be either ‘#’ or one of the nine non-zero digits. There will be at least one non-obstacle squares (i.e. squares with a non-zero digit in it) in the maze. The input is terminated by a test case with R=C=0R=C=0, you should not process it.

Output

For each test case, print the biggest number you can find, on a single line.

Samples

Input 复制

3 7
##9784#
##123##
##45###
0 0

Output

791452384

描述
你有一个有障碍物和非零数字的迷宫：
你可以从任何一个广场出发，在迷宫中漫步，最后在某个广场停下来。每一步，你只能走进四个相邻的广场（上，下，左，右）之一，你不能走进障碍物或走进一个广场不止一次。当你完成时，你可以把你遇到的数字按你遇到它们的相同顺序写下来，得到一个数字。例如，您可以得到数字9784、4832145等。您可以得到的最大数字是791452384，如上图所示。
你的任务是找到你能得到的最大数目。
输入
最多有25个测试用例。每个测试从两个整数R和C（2）开始≤R、 C级≤15，右∗C≤30），迷宫的行数和列数。接下来的R行代表迷宫。每行正好包含C字符（不带前导或尾随空格），每一个字符将是“#”或九个非零数字中的一个。迷宫中至少有一个非障碍方块（即其中有一个非零数字的方块）。输入被一个R=C=0的测试用例终止，您不应该处理它。
输出
对于每个测试用例，在一行上打印您能找到的最大数字。
样品
输入复制
3 7
##9784#
##123##
##45###
0 0
输出
791452384

方法：

直接dfs每一个数字，在每一层dfs中，加上bfs 判断剩下的数连接起来能否大于当前的ans 不能的话 剪枝了

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#define Siz(x) (int)x.size()
using namespace std;
 
const int maxn = 30 + 7;
 
int anslen;
string ans;
 
int q[10000000 + 7], L, R;
 
void camp(string& ss){
    int len = Siz(ss);
    if (len > anslen) {
        ans = ss;
        anslen = len;
    }
    else if (len == anslen && ans < ss) ans = ss;
}
 
int n,m;
 
char s[maxn][maxn];
 
bool vis[maxn][maxn];
 
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,-1,1};
 
bool bfs_vis[maxn][maxn];
 
bool cmp(char& ch1,char& ch2){
    return ch1 > ch2;
}
 
bool not_go(int &x_,int &y_,string &o){
    L = R = 0;
    q[R++] = x_ * 100+y_;
    memset(bfs_vis,0,sizeof bfs_vis);
    bfs_vis[x_][y_] = 1;
    string tmp = o;
    while(L < R){
        int oo = q[L++];
        int y = oo%100; oo-=y;
        int x = oo/100;
        for (int i = 0; i < 4; ++i){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] != '#' && !vis[xx][yy] && !bfs_vis[xx][yy]){
                bfs_vis[xx][yy] = 1;
                tmp += s[xx][yy];
                q[R++] = (xx*100+yy);
 
            }
        }
    }
    int len = Siz(tmp);
    if (len < anslen) return 1;
    else if (len == anslen){
        int olen = Siz(o);
        sort(tmp.begin()+olen,tmp.end(),cmp);
        if (tmp <= ans) return 1;
        return 0;
    }
    return 0;
}
void dfs(int x,int y,string o){
    if (anslen){
        if (not_go(x,y,o)) return;
    }
 
    bool ok = 0;
    for (int i = 0; i < 4; ++i){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] != '#' && !vis[xx][yy]){
            vis[xx][yy] = 1;
            ok = 1;
            dfs(xx,yy,o+s[xx][yy]);
            vis[xx][yy] = 0;
        }
    }
    if (!ok){
        camp(o);
    }
}
void init(){
    anslen = 0;
    ans= "";
}
int main(){
    while(~scanf("%d %d",&n, &m) && (n || m)){
        for (int i = 0; i < n; ++i){
            scanf("%s",s[i]);
        }
        init();
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (s[i][j] != '#'){
                    memset(vis,0,sizeof vis);
                    vis[i][j] = 1;
                    string a = "";
                    a += s[i][j];
                    dfs(i,j,a);
                }
            }
        }
        printf("%s\n",ans.c_str());
    }
    return 0;
}
 
/**
3 7
##9784#
##123##
##45###
0 0
791452384
**/