這幾天在做搜索，看到一篇比較好玩的論文，估價函數(shù)在信息學(xué)競賽中的應(yīng)用。發(fā)現(xiàn)有點難懂。好了，第一道就是uva10605。
題意就不廢話了。這題我剛剛看到作者列舉了下暴力時候深度為1-17的時候搜索的次數(shù)，我也很傻很天真的寫了個暴力。我是枚舉不定次數(shù)個邊界，然后找最小值。程序就一直在那兒搜，還沒用迭代加深搜索。。。傻傻寫了半小時。結(jié)果這種暴力中的最暴力需要的節(jié)點數(shù)太驚人了。然后就。。卡住了。
果斷搜。沒人寫這個題的結(jié)題報告。暈。偶然發(fā)現(xiàn)一個臺灣的網(wǎng)站，全死繁體字。找到了UVA10605，發(fā)現(xiàn)就一句話，最小生成樹變種云云，NPC問題。額，沒任何信息。額，也不是沒信息！最小生成樹算法是從每個節(jié)點開始枚舉，對，每個節(jié)點。。。額。。。。SB了，這個題直接暴力的寫法應(yīng)該是枚舉N個金礦，然后搜。
又很傻很天真的寫了一次。發(fā)現(xiàn)我寫的和作者列舉的生成結(jié)點個數(shù)差不多，列舉了幾個答案，也是對的。枚舉總算沒問題了。精彩的地方還在后面：如何用
。這題的意思。。額。。不難懂。以前看這個題沒思路，現(xiàn)在看了看，發(fā)現(xiàn)可以暴力一下。這個題應(yīng)該不是傳統(tǒng)意義上的搜索題，因為限制條件比較奇怪：兩條線不能交叉。而且數(shù)據(jù)很大，有100個點。而且還有無解情況。無解現(xiàn)在看來是沒辦法預(yù)判的，那么就要搜索所有的可能了。4^100是個天文數(shù)字。好吧，我沒有注意到任意兩條線不能相交這個題目條件，所以寫了個暴力，這個暴力也不是毫無價值，其實主要是想自己寫一個啟發(fā)函數(shù)試一試，看看能不能對這個問題進行優(yōu)化的。這個題的啟發(fā)函數(shù)很挫，就是所有的點到它最近的邊的長度（
#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;
}