原题大意

又是走迷宫的题目,不过这题有点不一样,因为要求狗狗要在T时刻恰好走到D处.

算法分析

明显dfs,不过直接深搜很快就会发现超时了,所以一定得剪枝,百度了下,除了剩余最短步数大于剩余时间外还有一个奇偶剪枝.

程序代码

#include <iostream>
#include <math.h>
#include <memory.h>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n,m,t;//对应N,M,T 
char maze[7][7];//迷宫 
bool used[7][7];
struct Point{
    int x,y;
};
Point start,door;
int flag;
void dfs(int x,int y,int time)
{

    if(flag) return ;//如果找到就return!否则容易超时     
    if(time>t) return;
    if(x==door.x&&y==door.y&&time==t) 
    {
        flag=1;
        return ;
    }
    for(int i=0;i<4;i++)
    {
        Point tt;
        tt.x=x+dx[i];
        tt.y=y+dy[i];
        if(tt.x<0||tt.y<0||tt.x>=n||tt.y>=m) continue;
        if(maze[tt.x][tt.y]=='X') continue;
        if(!used[tt.x][tt.y])
        {
            used[tt.x][tt.y]=1;
            dfs(tt.x,tt.y,time+1);    
            used[tt.x][tt.y]=0;
        }    
    }
    return ;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&t)&&n&&m&&t)
    {
        for(int i=0;i<n;i++)
                scanf("%s",maze[i]);
        for(int i=0;i<n;i++)

            for(int j=0;j<m;j++)
                {
                    if(maze[i][j]=='S')
                        {
                            start.x=i;
                            start.y=j;
                        }        
                    else if(maze[i][j]=='D')
                        {
                            door.x=i;
                            door.y=j;
                        }
                }
    if(abs(start.x-door.x)+abs(start.y-door.y)>t||(start.x+start.y+door.x+door.y+t)%2==1)//剪枝
    {
        printf("NO\n");
        continue;
    }
    memset(used,0,sizeof(used));
    flag=0;
    used[start.x][start.y]=1;
    dfs(start.x,start.y,0);
    if(flag) printf("YES");
    else printf("NO");
    printf("\n");
    }
    return 0;
}