题意就不废话了。这题我刚刚看到作者列举了下暴力时候深度为1-17的时候搜索的次数，我也很傻很天真的写了个暴力。我是枚举不定次数个边界，然后找最小值。程序就一直在那儿搜，还没用迭代加深搜索。。。傻傻写了半小时。结果这种暴力中的最暴力需要的节点数太惊人了。然后就。。卡住了。
果断搜。没人写这个题的结题报告。晕。偶然发现一个台湾的网站，全死繁体字。找到了UVA10605，发现就一句话，最小生成树变种云云，NPC问题。额，没任何信息。额，也不是没信息！最小生成树算法是从每个节点开始枚举，对，每个节点。。。额。。。。SB了，这个题直接暴力的写法应该是枚举N个金矿，然后搜。
。这题的意思。。额。。不难懂。以前看这个题没思路，现在看了看，发现可以暴力一下。这个题应该不是传统意义上的搜索题，因为限制条件比较奇怪：两条线不能交叉。而且数据很大，有100个点。而且还有无解情况。无解现在看来是没办法预判的，那么就要搜索所有的可能了。4^100是个天文数字。好吧，我没有注意到任意两条线不能相交这个题目条件，所以写了个暴力，这个暴力也不是毫无价值，其实主要是想自己写一个启发函数试一试，看看能不能对这个问题进行优化的。这个题的启发函数很挫，就是所有的点到它最近的边的长度（
#include <cstdio>
#include <cstring>
char map[20][20];
int vis[20][20];
class node
{
public:
int x,y;
};
node point[23];
int pcount;
int res;
int N,M;
int val[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int testdata;
int bound(
int x,
int y)
{
if(x<0 || y<0 || x>=N || y>=M)
return 0;
return 1;
}
int min(
int x,
int y)
{
if(x>y)
return y;
return x;
}
int getH()
{
int i,ret = 0;
for(i=0;i<pcount;i++)
{
int x = point[i].x;
int y = point[i].y;
if(!vis[x][y])
{
ret += min(min(x,N-x),min(y,M-y));
}
}
return ret;
}
void dfs(
int step,
int x,
int y,
int next,
int F,
int count,
int maxstep)
{
testdata++;
if(step > maxstep)
return;
if(next == pcount)
{
if(count == pcount && res > step)
{
res = step;
}
return;
}
int i;
if(F == 1)
{
if(!vis[point[next].x][point[next].y])
{
vis[point[next].x][point[next].y] = 1;
dfs(step+1,point[next].x,point[next].y,next+1,0,count+1,maxstep);
vis[point[next].x][point[next].y] = 0;
}
dfs(step,0,0,next+1,1,count,maxstep);
return;
}
else {
for(i=0;i<4;i++)
{
int nx = x + val[i][0];
int ny = y + val[i][1];
if(bound(nx,ny) && !vis[nx][ny])
{
if(map[nx][ny] != '#')
{
vis[nx][ny] = 1;
if(map[nx][ny] == '*')
dfs(step+1,nx,ny,next,0,count+1,maxstep);
else dfs(step+1,nx,ny,next,0,count,maxstep);
vis[nx][ny] = 0;
}
else dfs(step,0,0,next,1,count,maxstep);
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j;
while(scanf("%d%d",&N,&M)!=EOF)
{
pcount = 0;
for(i=0;i<N;i++)
scanf("%s",map[i]);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(map[i][j] == '*')
{
node tmp ={i,j};
point[pcount++] = tmp;
}
memset(vis,0,
sizeof(vis));
res = N*M;
testdata = 0;
for(i=1;i<=16;i++)
{
dfs(0,0,0,0,1,0,i);
if(res == i)
{
printf("%d %d\n",res,testdata);
break;
}
}
}
return 0;
}