HDU 2579 (记忆化BFS搜索)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2579

题目大意:走迷宫。对于障碍点,只有当前(dep+1)%k才能走,问最少时间。

解题思路

只有一个关键:

每个点不是只可以走一次。最多可以走k次。

原因是对于一个点,可能是通过障碍点在k的倍数(即余数为0)步到达的,也可能是通过其它途径到达的,但是不是k的倍数(余数为1~k)。

这样,判断状态是否重叠的依据就是看在(x,y)点的余数状态了。vis的第三维非常重要。

#include "cstdio"
#include "string"
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;
int n,m,k,sx,sy,ex,ey,T,vis[105][105][15],dir[4][2]={-1,0,1,0,0,-1,0,1};
char map[105][105];
struct status
{
    int x,y,dep;
    status(int x,int y,int dep):x(x),y(y),dep(dep) {}
};
int bfs(int x,int y)
{
    queue<status> Q;
    Q.push(status(x,y,0));
    vis[x][y][0]=true;
    while(!Q.empty())
    {
        status t=Q.front();Q.pop();
        for(int s=0;s<4;s++)
        {
            int X=t.x+dir[s][0],Y=t.y+dir[s][1],dep=t.dep+1;
            if(X<1||X>n||Y<1||Y>m) continue;
            if(map[X][Y]=='#')
            {
                if(dep%k==0&&!vis[X][Y][dep%k])
                {
                    vis[X][Y][dep%k]=true;
                    Q.push(status(X,Y,dep));
                }
            }
            else
            {
                if(vis[X][Y][dep%k]) continue;
                if(X==ex&&Y==ey) return dep;
                vis[X][Y][dep%k]=true;
                Q.push(status(X,Y,dep));
            }
        }
    }
    return -1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    string tt;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>tt;
            for(int j=0;j<tt.size();j++)
            {
                map[i][j+1]=tt[j];
                if(tt[j]=='Y') {sx=i;sy=j+1;}
                if(tt[j]=='G') {ex=i;ey=j+1;}
            }
        }
        int ans=bfs(sx,sy);
        if(ans==-1) cout<<"Please give me another chance!"<<endl;
        else cout<<ans<<endl;
    }
}
11899492 2014-10-18 10:10:31 Accepted 2579 0MS 964K 1734B C++ Physcal
原文地址:https://www.cnblogs.com/neopenx/p/4032753.html