UVA - 11882 Biggest Number(dfs+bfs+强剪枝)

题目大意：给出一个方格矩阵，矩阵中有数字0~9，任选一个格子为起点，将走过的数字连起来构成一个数，找出最大的那个数，每个格子只能走一次。

题目分析：DFS。剪枝方案：在当前的处境下，找出所有还能到达的点的个数，若当前数字的长度加上个数仍小于目前最优答案的长度，则剪去；若长度相等，则将所有还能到达的数字按从大到小排序后连到当前数字上，如果还比目前最优解小，则减去。找出所有还能到达的点的过程用BFS实现。

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<bitset>

 #include<map>

 #include<vector>

 #include<stdlib.h>

 #include <stack>

 using namespace std;

 #define PI acos(-1.0)

 #define max(a,b) (a) > (b) ? (a) : (b)

 #define min(a,b) (a) < (b) ? (a) : (b)

 #define ll long long

 #define eps 1e-10

 #define MOD 1000000007

 #define N 16

 #define M 36

 #define inf 1e12

 int n,m;

 char mp[N][N];

 int vis[N][N];

 int flag[N][N];

 int can[N<<];

 int dirx[]={,,-,};

 int diry[]={-,,,};

 string ans;

 bool smaller(string a,string b){

      if(a.size()<b.size()) {

          return true;

      }

      if(a.size()==b.size()){

         if(a<b){

            return true;

         }

      }

      return false;

 }

 bool ok(int x,int y){

      if(x< || x>=n || y< || y>=m || mp[x][y]=='#') return false;

      return true;

 }

 int bfs(int x,int y){

      queue<int> q;

      q.push(x*M+y);

      memset(flag,,sizeof(flag));

      flag[x][y]=;

      int step=;

      while(!q.empty()){

          int t=q.front();

          q.pop();

          for(int i=;i<;i++){

              int tx=t/M; int ty=t%M;

              tx+=dirx[i]; ty+=diry[i];

              if(vis[tx][ty] || flag[tx][ty] || !ok(tx,ty)) continue;

              can[step++]=mp[tx][ty]-'';

              flag[tx][ty]=;

              q.push(tx*M+ty);

          }

      }

      return step;

 }

 void dfs(int x,int y,string tmp){

      if(smaller(ans,tmp)){

          ans=tmp;

      }

      int get_step=bfs(x,y);

      if(get_step+tmp.size()<ans.size()){

          return;

      }

      if(get_step+tmp.size()==ans.size()){

          sort(can,can+get_step);

          string now=tmp;

          for(int i=get_step-;i>=;i--){

              now+=char(can[i]+'');

          }

          if(smaller(now,ans)){

             return;

          }

      }

      for(int i=;i<;i++){

          int tx=x+dirx[i];

          int ty=y+diry[i];

          if(vis[tx][ty] || !ok(tx,ty)) continue;

          vis[tx][ty]=;

          dfs(tx,ty,tmp+mp[tx][ty]);

          vis[tx][ty]=;

      }

 }

 int main()

 {

    while(scanf("%d%d",&n,&m)==){

         if(n== && m==){

             break;

         }

         for(int i=;i<n;i++){

            scanf("%s",mp[i]);

         }

         ans.clear();

         memset(vis,,sizeof(vis));

         for(int i=;i<n;i++){

             for(int j=;j<m;j++){

                 if(mp[i][j]!='#'){

                    vis[i][j]=;

                    string tmp; tmp.clear();

                    tmp+=mp[i][j];

                    dfs(i,j,tmp);

                    vis[i][j]=;

                 }

             }

         }

         cout<<ans<<endl;

    }

     return ;

 }