Hero In Maze 简单版

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。

突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。

请你判断他是否能救出心爱的公主。(假设有路可以通到公主那就可以找到公主)。

输入

题目包括多组测试数据。

每组测试数据以两个整数n,m(0<n, m≤20)开头，分别代表迷宫的长和高。紧接着有m行，n列字符，由"."，"*"，"P"，"S"组成。其中

"." 代表能够行走的空地。

"*" 代表墙壁，Jesse不能从此通过。

"P" 是公主所在的位置。

"S" 是Jesse的起始位置。

Jesse只能选择“上、下、左、右”任意一方向走一步。

输入以0 0结束。

输出

如果能救出公主输出“YES”，否则输出“NO”。

样例输入

4 4

....

S**P

4 4

....

****

S**P

0 0

样例输出

YES

#include<iostream>  
#include<cstring>  
#include<cstdio>  
using namespace std;  
int n,m;  
char a[21][21];  
int s[3],p[3];  
bool flag=false;  
int q[4][2]={0,1,1,0,0,-1,-1,0};  
int dfs(int x,int y)  
{  
    if(x==p[0]&&y==p[1]){flag=true;return 0;}  
    for(int i=0;i<4;i++)  
    {  
        int dx=x+q[i][0];  
        int dy=y+q[i][1];  
        if(dx>=1&&dx<=m&&dy>=1&&dy<=n&&a[dx][dy]!='*')  
        {  
            a[dx][dy]='*';  
            dfs(dx,dy);  
            a[dx][dy]='.';  
        }  
    }  
    return 0;  
}  
int main()  
{  
  
    while(~scanf("%d%d",&n,&m),n||m)  
    {  
        flag=false;  
        int ss=0;  
        for(int i=1;i<=m;i++)  
            for(int j=1;j<=n;j++)  
            {  
                cin>>a[i][j];  
                if(a[i][j]=='S'){s[0]=i;s[1]=j;}  
                if(a[i][j]=='P'){p[0]=i;p[1]=j;}  
                if(a[i][j]=='*')ss=1;  
            }  
            if(ss==0){cout<<"YES"<<endl;continue;}  
            dfs(s[0],s[1]);  
            if(flag==true)cout<<"YES"<<endl;  
            else cout<<"NO"<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,