Hero In Maze

时间限制(普通/Java):1000MS/10000MS          执行内存限制:65536KByte

描写叙述

500年前，Jesse是我国最卓越的剑客。

他英俊潇洒，并且机智过人^_^。

突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。

Jesse听说这个消息已经是两天以后了，他知道公主在迷宫中还能坚持T天，他急忙赶到迷宫，開始到处寻找公主的下落。

时间一点一点的过去。Jesse还是无法找到公主。

最后当他找到公主的时候，漂亮的公主已经死了。从此Jesse郁郁寡欢，茶饭不思。一年后追随公主而去了。T_T

500年后的今天，Jesse托梦给你，希望你帮他推断一下当年他是否有机会在给定的时间内找到公主。

他会为你提供迷宫的地图以及所剩的时间T。

请你推断他能否救出心爱的公主。

输入

题目包含多组測试数据。

每组測试数据以三个整数N,M,T(0<n, m≤20, t>0)开头，分别代表迷宫的长和高，以及公主能坚持的天数。

紧接着有M行。N列字符，由"."，"*"。"P"，"S"组成。

当中

"." 代表可以行走的空地。

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

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

"S" 是Jesse的起始位置。

每一个时间段里Jesse仅仅能选择“上、下、左、右”随意一方向走一步。

输入以0 0 0结束。

输出

假设能在规定时间内救出公主输出“YES”，否则输出“NO”。

例子输入

4 4 10

....

....

....

S**P

0 0 0

例子输出

YES

AC代码例如以下

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 1000005#define ll long longusing namespace std;int DTx[4]={-1,0,1,0};int DTy[4]={0,1,0,-1};char map[25][25];int dp[25][25];int x,y,X,Y;int minn;int n,m,t;struct H{ int x,y; int time;};int bfs(int h,int z){ int i,j; queue 
           
             q; H a,b,c; a.x=h; a.y=z; a.time=0; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); if(b.x==X&&b.y==Y) return b.time; for(i=0;i<4;i++) { c.x=b.x+DTx[i]; c.y=b.y+DTy[i]; if(c.x>=0&&c.x
            
             =0&&c.y
             
              >map[i]; for(i=0;i