WOJ1041-Magic Forest

MagicForest has many trees, such as linetree , suffix-tree , red-black tree.... Do you master all the trees?

But don't worry, in this problem I will not talk about trees.Instead, I am going to introduce some animals in MagicForest. The first is kingkong.
Kingkong is one kind of dangerous animals. So if you meet kingkong , you will die. The second is mathdog. Mathdog is a wild dog, but it is not
so dangerous as kingkong. It will only bite you.
Amaze is a beautiful girl. Unfortunately she is lost in MagicForest, and of course Magicpig worrys about her very much. Magicpig knows that
if he meets kingkongs, he will die. He also knows that mathdogs will bite him, and after two bites of mathdogs(including two), Magicpig will also
die. How poor Magicpig is!

输入格式

The first line of the input is a single number t (0<t<20) , indicating the number of test cases.

Each test case is a map of MagicForest preceded by a line with a number n(0<n<=30). MagicForest is a matrix of n * n cells:
(1) "p" means Magicpig. (2) "a" means Amaze. (3) "r" means road. (4) "k" means kingkong. (5) "d" means mathdog . Note that Magicpig can only move in four directions : up, down , left, right.

输出格式

For each test case, if Magicpig can find Amaze output "Yes" in a line, or output "No" in a line.

样例输入

4
3
pkk
rrd
rda
3
prr
kkk
rra
4
prrr
rrrr
rrrr
arrr
5
prrrr
ddddd
ddddd
rrrrr
rrrra

样例输出

Yes
No
Yes
No

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 32
char maze[SIZE][SIZE];
int state[SIZE][SIZE];
typedef struct node{
  	int x, y, life;
}node;
node stack[100000];
int top;//栈顶指针 
int size,sx,sy;
int inside(node a){
  	return (a.x >= 0 && a.x < size && a.y >= 0 && a.y < size);
}
int dfs1(node cur);
int go(node cur, int dx, int dy){
  	node next = cur;
  	char t;
  	next.x += dx;
  	next.y += dy;
  	if(!inside(next))return 0;
  	if(state[next.x][next.y] >= next.life)return 0;
  	t = maze[next.x][next.y];
  	if(t == 'k') return 0;
  	if(t == 'd') next.life--;
  	return dfs1(next);
}
int dfs1(node cur){
 	if(cur.life <= 0)return 0;
  	if(maze[cur.x][cur.y] == 'a')return 1;
  	stack[top++]=cur;
  	state[cur.x][cur.y]=cur.life;
  	if(go(cur, -1, 0))return 1;
  	if(go(cur, 0, -1))return 1;
  	if(go(cur, 1, 0))return 1;
  	if(go(cur, 0, 1))return 1;
  	top--;
  	return 0;
}
int main(){
	int cases,i,j;
	scanf("%d", &cases);
	while(cases--){
    	scanf("%d", &size);
  		for(i = 0; i < size; i++){
    		scanf("%s", maze[i]);
    		for(j = 0; j < size; j++){
      			state[i][j] = 0;
      			if(maze[i][j] == 'p'){
        			sx = i, sy = j;
      			}
    		}
  		}
	    node start = {sx, sy, 2};
    	if(dfs1(start))
    		printf("Yes\n");
    	else
      		printf("No\n");
	}
	return 0;  
}