uva11882Biggest Number（DFS + 剪枝）

题意：给一个矩阵，里面有#和数字，问你一笔画能得到的最大数字是多少

思路：我一开始的思路是先把#去掉再建一个新图，然后就相当于在这个图中找哈密顿路，给边大到小排序，枚举大的边求哈密顿路，如果找到就一定是最大的了，如果找不到就去掉一个小的顶点继续找哈密顿路.....YY了许久发现复杂度好高...而且程序不会写....gg,后来搜了一下题解发现了一个剪枝，就是如果答案长度和格子数一样的时候，如果第一位小于已经搜出来的答案，那么以这个数字为开头就不用搜了，就加上这个优化就能过掉

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
using namespace std;
#define maxn 100000
#define LL long long
int cas=1,T;
int n,m,vis[35],cnt;
char a[35],ans[35];
int anslen;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char s[16][16];
char ss[35];
vector<int> g[35];
void dfs(int cur,int len)
{
	bool ok = false;
	for (int i = 0;i<g[cur].size();i++)
	{
		int v = g[cur][i];
		if (!vis[v])
		{
			ok = true;
			vis[v]=1;
			a[len]=ss[v];
			dfs(v,len+1);
			vis[v]=0;
		}
	}
	if (ok)
		return ;
	a[len]='\0';
	if (len > anslen)
	{
		anslen = len;
		memcpy(ans,a,sizeof(a));
	}
	else if (len == anslen)
	{
		if (memcmp(a,ans,sizeof(a)) > 0)
			memcpy(ans,a,sizeof(a));
	}
	return;
}
int main()
{
	while (scanf("%d%d",&n,&m))
	{
		if (!n && !m)break;
		for (int i = 1;i<=n;i++)
		  scanf("%s",s[i]+1);
		int x[35],y[35],id[16][16];
		cnt = 0;
        for (int i = 1;i<=n;i++)
		{
			for (int j = 1;j<=m;j++)
			{
				if (s[i][j] !='#')
				{
					x[cnt]=i;
					y[cnt]=j;
					ss[cnt]=s[i][j];
					id[i][j]=cnt++;
				}
			}
		}
        
		for (int i = 0;i<cnt;i++)
			g[i].clear();
		for (int i = 0;i<cnt;i++)
		{
			for (int j = 0;j<4;j++)
			{
				int r = x[i]+dir[j][0];
				int c = y[i]+dir[j][1];
		   		if (r<1 || r>n || c<1 || c>m)
					continue;
				if (s[r][c]!='#')
					g[i].push_back(id[r][c]);
			}
		}
        anslen = 0;
		memset(vis,0,sizeof(vis));
		for (int i = 0;i<cnt;i++)
		{
			if (anslen==cnt && ss[i]<ans[0])  //剪枝
				continue;
			vis[i]=1;
			a[0]=ss[i];
			dfs(i,1);
			vis[i]=0;
		}
		printf("%s\n",ans);
	}
	//freopen("in","r",stdin);
	//scanf("%d",&T);
	//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}