心得体会"/>
hdu 1010 的心得体会
此题大意:从S走到D,要求恰好为T步,地图中点为路,X为墙(不能通过)。 感觉一脸懵逼,手足无措。 就只有采用搜索这样的方法才可以维持得了生命,搜索简单而又实用,我超喜欢待在里面的。 搜索就像一堆警察在一片树林里逮一个强奸犯,警察掌握了一些信息但是又不可能知道歹徒的具体位置。 深度优先搜索就是一条路或者说一个方向搜到底(直到前面有悬崖或者歹徒找到了),广度优先搜索就是那种地毯式搜索(100个人站一排向前突进)。 此题采用深度优先搜索的方法,要注意满足哪些条件就不用搜这条路了(吾乃天命之子,可预知悬崖。。。 ) 奇偶剪枝(名字倒是取得很6,淫才):如多从一个点到另一个点的最短距离是偶数,那么所有路径都是偶数,所以此时奇数步走完是不可能的。(自己领悟去吧,领悟了记得评论告我咋这么神奇呢.............) 嗯........剩下的细节看代码吧。。溜了 #include<iostream>using namespace std;
char map[8][8];
int direction[2][4]={0,1,0,-1,
1,0,-1,0};
int flag;
int N,M,T,ex,ey; //end x,y
int point; //点的个数
int abs(int x)
{
return x>0?x:-x;
}
void f(int sx,int sy,int num)
{
int shortdi;//short distance 最短距离
int x,y;
int mark;
if(flag==1)return;
if(sx==ex&&sy==ey&&num!=T)return;
if(sx==ex&&sy==ey&&num==T)
{
flag=1;
return;
}
shortdi=abs(sx-ex)+abs(sy-ey);
if((shortdi+T-num)%2||T-num<shortdi)return;
for(int i=0;i<4;i++)
{
if(map[sx][sy]=='.'){mark=1;map[sx][sy]='X';}
else mark=0;
x=sx;y=sy;
x+=direction[0][i];
y+=direction[1][i];
if(x>=0&&x<N&&y>=0&&y<M&&(map[x][y]=='.'||map[x][y]=='D'))
{
f(x,y,num+1);
}
if(mark)map[sx][sy]='.';
}
}
int main()
{
int sx,sy; //start x,y
while(cin>>N>>M>>T)
{
if(N==0&&M==0&&T==0)break;
point=0;
flag=0;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
sx=i;
sy=j;
}
if(map[i][j]=='D')
{
ex=i;
ey=j;
}
if(map[i][j]=='.')
point++;
}
}
if(point<T-1)
{
cout<<"NO\n";
continue;
}
f(sx,sy,0);
if(flag==1)cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
} //Number 1
更多推荐
hdu 1010 的心得体会
发布评论