題目：Biggest Number

題意：

在一個R行C列（2≤R，C≤15，R*C≤30）的矩陣里有障礙物和數字格（包含1～9的數字）。 你可以從任意一個數字格出發，每次沿著上下左右之一的方向走一格，但不能走到障礙格中，也不能重復經過一個數字格，然后把沿途經過的所有數字連起來，問：能得到的最大整數是多少？

思路：

還是老套路，dfs尋找所有路徑，累計篩選最大的數即可，恩，很簡單嘛。。。提交，TLE，呵呵，數字太大了！所以剪枝來了。。。

本題的連接數字已經超出了long long型，所以需要用字符串，所以首先比較的是長度，長度越長即越大！！！

剪枝1：當前已經連接的數的個數+還可連接的數的個數  < 當前最優解的長度，直接剪枝，沒有必要再搜索下去！

怎么找還可連接的數的個數呢？   利用bfs，使用當前的標記數組，搜索出還可連接的個數即可。

剪枝2：當前已經連接的數的個數+還可連接的數的個數  == 當前最優解的長度時，比較大小，小直接剪掉。只比較當前連接的數的長度這些數字，將當前的串加上一個比數字字符大的字符即可。因為有可能當前串和最優解的都相等，但最優解串長，就直接認為是最優解大了，其實當前還不確定，所有再當前串的下一位加一個大于數字的字符，這樣避免了相等也被剪枝的情況！篩選最優解：每次遞歸時將當前串進行與最優解比較長度，如果相等的話再比較大小。

參考：ECNU_ZR博客

代碼：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long LL;const int maxn = 20 + 5;const int dx[] = {0,0,1,-1};const int dy[] = {1,-1,0,0};char g[maxn][maxn];int visitD[maxn][maxn],visitB[maxn][maxn];int r,c;string ans,temp;struct Node{    int x,y;    Node(int x = 0,int y = 0):x(x),y(y){}};queue<Node>Q;inline bool scope(int tx,int ty){//判斷邊界    if(tx < 0 || tx >= r || ty < 0 || ty >= c) return true;    return false;}int bfs(int x,int y){//查找當前(x,y)開始還可以連接幾個數字    memcpy(visitB,visitD,sizeof(visitD));//將當前dfs標記數組賦給bfs標記數組    visitB[x][y] = 1;//標記起點    while(!Q.empty()) Q.pop();//清空隊列    Node PRe;    Q.push(Node(x,y));//將起點入隊    int cnt = 0;//記錄經過幾個點    while(!Q.empty()){        pre = Q.front();Q.pop();        for(int i=0;i<4;i++){            int tx = pre.x + dx[i] , ty = pre.y + dy[i];            if(scope(tx,ty)) continue;            if(g[tx][ty] != '#' && !visitB[tx][ty]){                visitB[tx][ty] = 1;                Q.push(Node(tx,ty));                cnt++;//記錄連接到的數字個數            }        }    }    return cnt;//返回剩余的連接個數}void update(const string &s){//更新最優解：當前長度長或長度相等數字大時更新    if(s.size() > ans.size() || s.size() == ans.size() && s > ans) ans = s;}void dfs(int d,int x,int y,string sum){//回溯枚舉所有連接路徑    int len = bfs(x,y);//當前點還可連接的數的個數    if(d + len < ans.size()) return;//剪枝：當前的長度+還可連接的長度 < 最優值的長度，沒有必要再進行下去    if(d + len == ans.size() && sum+"a" < ans) return;//剪枝：長度相等，但沒有最優解大，沒有不必了！    update(sum);//更新最優解    for(int i=0;i<4;i++){        int tx = x + dx[i] , ty = y + dy[i];        if(scope(tx,ty)) continue;        if(!visitD[tx][ty] && g[tx][ty] != '#'){            visitD[tx][ty] = 1;            dfs(d+1,tx,ty,sum + g[tx][ty]);            visitD[tx][ty] = 0;        }    }}inline void solve(){    ans = "";    for(int i=0;i<r;i++)        for(int j=0;j<c;j++)            if(g[i][j] != '#'){                memset(visitD,0,sizeof(visitD));                visitD[i][j] = 1;//注意：將起點標記                temp = g[i][j];                dfs(1,i,j,temp);            }    cout << ans << endl;}int main(){    while(scanf("%d%d",&r,&c)!=EOF && r && c){        for(int i=0;i<r;i++) scanf("%s",g[i]);        solve();    }    return 0;}