题解 P2298 【Mzc和男家丁的游戏】

doby · 2016-11-17 22:46:45 · 题解

bfs+hash过关……

不是很难……

#include<iostream>
#include<cstdlib>
using namespace std;
int sum,data[2000007],list[2000007]={0},next[2000007]={0},u,tim[3000000],qs[3000000],a[2009][2009],head=0,tail=1,n,m,t,c,cnt=0,x,y,x1,y1,x2,y2,x3,y3,fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
char k;
int hash(int h)//hash
{
    sum=abs(h%1000007),u=list[sum];
    while(u){if(data[u]==h){return 0;}u=next[u];}
    data[++cnt]=h,next[cnt]=list[sum],list[sum]=cnt;
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>k;//输入+处理
            if(k=='#'){a[i][j]=1;}
            if(k=='.'){a[i][j]=0;}
            if(k=='m'){x1=i,y1=j;}
            if(k=='d'){x2=i,y2=j;}
        }
    }
    qs[1]=x1*10000+y1,tim[1]=0;//存入初始状态
    while(head<tail)
    {
        head++,x=qs[head]/10000,y=qs[head]-x*10000,t=tim[head];//取出状态
        for(int i=0;i<4;i++)
        {
            x3=x+fx[i],y3=y+fy[i];//走出一步
            if(x3<1||x3>n||y3<1||y3>m||a[x3][y3]==1){continue;}//出界+障碍
            if(x3==x2&&y3==y2){cout<<t+1;return 0;}//得出结果
            if(hash(x3*10000+y3)){tail++,qs[tail]=x3*10000+y3,tim[tail]=t+1;}//入队
        }
    }
    cout<<"No Way!";
    return 0;
}