hdu 4230 bfs+記憶化搜索

hdu 4230 bfs+記憶化搜索

告訴你從起點到終點最短步數的方式有多少種；

mark表示每個點對應每個方向的最小步數；

num表示種樹；

然後按照題意搜就行

#include
#include
#include
#include
using namespace std;

#define INF 0x3f3f3f3f
struct node
{
    int x,y,step;
    int d;
}a,b;
int n,m;
char map[110][110];
int mark[110][110][5];
int num[110][110][5];
int dir[4][2]={-1,0,0,1,1,0,0,-1};
queue<node>q;
int deal(node next,node cur)
{
    if(next.step<mark[next.x][next.y][next.d])
    {
        mark[next.x][next.y][next.d]=next.step;
        num[next.x][next.y][next.d]=num[cur.x][cur.y][cur.d];
        num[next.x][next.y][next.d]%=1000000;
        q.push(next);
    }
    else if(next.step==mark[next.x][next.y][next.d])
    {
        num[next.x][next.y][next.d]+=num[cur.x][cur.y][cur.d];
        num[next.x][next.y][next.d]%=1000000;
    }    
    return 0;
}
int bfs(int x,int y,int d)
{
    memset(mark,INF,sizeof(mark));
    memset(num,0,sizeof(num));
    a.x=x;
    a.y=y;
    a.step=0;
    a.d=d;
    mark[a.x][a.y][a.d]=0;
    num[a.x][a.y][a.d]=1;
    //queueq;
    q.push(a);
    while(!q.empty())
    {
        b=q.front();
        q.pop();
        a=b;
        if(b.d==1) a.d=4;
        else if(b.d==2) a.d=1;
        else if(b.d==3) a.d=2;
        else if(b.d==4) a.d=3;
        a.step=b.step+1;
        deal(a,b);
        a=b;
        if(b.d==1) a.d=2;
        else if(b.d==2) a.d=3;
        else if(b.d==3) a.d=4;
        else if(b.d==4) a.d=1;
        a.step=b.step+1;
        deal(a,b);
        for(int i=1;;i++)
        {
            a.x=b.x+i*dir[b.d-1][0];
            a.y=b.y+i*dir[b.d-1][1];
            a.step=b.step+1;
            a.d=b.d;
            if(a.x<0||a.x>=n||a.y<0||a.y>=m) break;
            if(map[a.x][a.y]=='*') break;
            deal(a,b);
        }
    }
    return 0;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        for(i=0;i<n;i++)
        scanf("%s",map[i]);
        int ex,ey;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(map[i][j]=='N') bfs(i,j,1);
                else if(map[i][j]=='E') bfs(i,j,2);
                else if(map[i][j]=='S') bfs(i,j,3);
                else if(map[i][j]=='W') bfs(i,j,4);
                else if(map[i][j]=='X')
                {
                    ex=i;
                    ey=j;
                }
            }
        }
        int Min=INF;
        for(i=0;i<=4;i++)
        if(mark[ex][ey][i]<Min) Min=mark[ex][ey][i];
        int t=0;
        for(i=1;i<=4;i++)
        if(mark[ex][ey][i]==Min) t+=num[ex][ey][i];
        if(Min==INF) printf("0 0\n");
        else printf("%d %d\n",Min,t%1000000);
    }
    return 0;
}