简单的迭代加深搜索求最优解。注意判断可以继续行走的条件。
以下是我的代码：
/*
* Author: lee1r
* Created Time: 2011/8/6 8:51:53
* File Name: poj3009.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(27);
const int dx[]={1,-1,0,0},dy[]={0,0,-1,1};
int n,m,s1,s2,g1,g2,r[kMaxn][kMaxn];
bool success;
int Check(int x,int y,int dir,int &xx,int &yy)
{
int t(0);
do
{
if(r[x][y]==3)
{
xx=x;
yy=y;
return 3;
}
else if(t<=1 && r[x][y]==1)
return 0;
else if(t>1 && r[x][y]==1)
{
xx=x;
yy=y;
return 1;
}
x+=dx[dir];
y+=dy[dir];
t++;
}while(x>=1 && x<=n && y>=1 && y<=m);
return 0;
}
void dfs(int depth,int x,int y,int maxdepth)
{
if(depth>maxdepth)
{
if(g1==x && g2==y)
success=true;
return;
}
for(int i=0;i<4;i++)
{
int newx,newy,result(Check(x,y,i,newx,newy));
if(result==1)
{
r[newx][newy]=0;
dfs(depth+1,newx-dx[i],newy-dy[i],maxdepth);
r[newx][newy]=1;
}
else if(result==3)
dfs(depth+1,newx,newy,maxdepth);
}
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d%d",&m,&n)==2 && (n || m))
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&r[i][j]);
if(r[i][j]==2)
{
s1=i;s2=j;
}
else if(r[i][j]==3)
{
g1=i;g2=j;
}
}
int ans;
success=false;
for(ans=1;ans<=10;ans++)
{
dfs(1,s1,s2,ans);
if(success)
break;
}
if(ans>10)
printf("%d\n",-1);
else
printf("%d\n",ans);
}
return 0;
}
posted on 2011-08-06 09:34
lee1r 阅读(283)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索