B - Help the Princess!
Time limit : 2sec / Memory limit : 512MB
Problem Statement
The people of a certain kingdom make a revolution against the bad government of the princess. The revolutionary army invaded the royal palace in which the princess lives. The soldiers of the army are exploring the palace to catch the princess. Your job is writing a program to decide that the princess can escape from the royal palace or not.
For simplicity, the ground of the palace is a rectangle divided into a grid. There are two kinds of cells in the grid: one is a cell that soldiers and the princess can enter, the other is a cell that soldiers or the princess cannot enter. We call the former an empty cell, the latter a wall. The princess and soldiers are in different empty cells at the beginning. There is only one escape hatch in the grid. If the princess arrives the hatch, then the princess can escape from the palace. There are more than or equal to zero soldiers in the palace.
The princess and all soldiers take an action at the same time in each unit time. In other words, the princess and soldiers must decide their action without knowing a next action of the other people. In each unit time, the princess and soldiers can move to a horizontally or vertically adjacent cell, or stay at the current cell. Furthermore the princess and soldiers cannot move out of the ground of the palace. If the princess and one or more soldiers exist in the same cell after their move, then the princess will be caught. It is guaranteed that the princess can reach the escape hatch via only empty cells if all soldiers are removed from the palace.
If there is a route for the princess such that soldiers cannot catch the princess even if soldiers make any moves, then the princess can escape the soldiers. Note that if the princess and a soldier arrive the escape hatch at the same time, the princess will be caught. Can the princess escape from the palace?
Input
Each dataset is formatted as follows.
HH WW
map1map1
:
:
mapHmapH
The first line of a dataset contains two positive integers HH and WW delimited by a space, where HH is the height of the grid and WW is the width of the grid. (2≤H,W≤2002≤H,W≤200)
The ii-th line of the subsequent HH lines gives a string mapimapi, which represents situation in the ground of palace.
mapimapi is a string of length WW, and the jj-th character of mapimapi represents the state of the cell of the ii-th row and the jj-th column.
'@', '$', '%', '.', and '#' represent the princess, a soldier, the escape hatch, an empty cell, and a wall, respectively. It is guaranteed that there exists only one '@', only one '%', and more than or equal to zero '$' in the grid.
Output
Output a line containing a word "Yes", if the princess can escape from the palace. Otherwise, output "No".
Sample Input 1
2 4 %.@$ ..$$
Output for the Sample Input 1
Yes
Sample Input 2
3 4 .%.. .##. .@$.
Output for the Sample Input 2
Yes
Sample Input 3
2 3 %$@ ###
Output for the Sample Input 3
No
Sample Input 4
2 3 @#$ .%.
Output for the Sample Input 4
No
Sample Input 5
2 2 @% ..
Output for the Sample Input 5
Yes
求出口到士兵和公主的最短距离，然后比较，如果公主较近，则可以逃脱
bfs
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp1 make_pair
#define fi first
#define se second
#define PI acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
//void dfs(int x,int y,int step);
void bfs(int x,int y,int flag2);
int flag,flag1;
typedef struct node{
int x;
int y;
int step;
}NODE;
NODE que[1000005];
int head,tail;
int h,w;
char mp[205][205];
int book[205][205];
int stx,sty,endx,endy;
int main()
{
flag=9999999,flag1=0;
memset(que,0,sizeof(que));
head = tail = 0;
memset(book,0,sizeof(book));
memset(mp,0,sizeof(mp));
h=read();
w=read();
for(int i=0;i<h;i++)
gets(mp[i]);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(mp[i][j]=='%')
{
stx=i;
sty=j;
}
}
}
bfs(stx,sty,1);
memset(que,0,sizeof(que));
head = tail = 0;
memset(book,0,sizeof(book));
bfs(stx,sty,0);
if(flag1 == 0)
{
printf("No");
return 0;
}
if(flag>flag1)
printf("Yes");
else
printf("No");
return 0;
}
void bfs(int x1,int y1,int flag2)
{
NODE t;
int xx,yy;
t.x=x1;
t.y=y1;
t.step=0;
que[tail++] = t;
while(head<tail)
{
//printf("%d %d\n",head,tail);
for(int i=0;i<4;i++)
{
xx = que[head].x+dir[i][0];
yy = que[head].y+dir[i][1];
if(xx<0||xx>=h||yy<0||yy>=w)
{
continue;
}
if(book[xx][yy]==1||mp[xx][yy]=='#')
continue;
if(flag2)
{
if(mp[xx][yy]=='$')
continue;
if(mp[xx][yy]=='@')
{
flag1 = que[head].step+1;
return ;
}
}
else
{
if(mp[xx][yy]=='@')
continue;
if(mp[xx][yy]=='$')
{
flag = que[head].step+1;
return ;
}
}
book[xx][yy]=1;
t.x=xx;
t.y=yy;
t.step=que[head].step+1;
que[tail++]=t;
}
head++;
}
}
/*void dfs(int x,int y,int step)
{
int xx,yy;
if(x==endx&&y==endy)
{
flag =1;
printf("step=%d\n",step);
return ;
}
for(int i=0;i<4;i++)
{
xx = x+dir[i][0];
yy = y+dir[i][1];
if(xx<0||xx>=h||yy<0||yy>=w)
{
continue;
}
if(book[xx][yy]==1||mp[xx][yy]=='#'||mp[xx][yy]=='$')
continue;
book[xx][yy]=1;
dfs(xx,yy,step+1);
book[xx][yy]=0;
}
}
*/