Felix021

WOJ1041 MagicForest解题报告 By Felix021

题目路径: http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1041

描述：给出一个N*N的矩阵，每个格子有a, p, r, d, k 5种状态，需要从p出发点到a点，初始生命值为2，r是一般通路，d使生命值减1，k使生命值减到0。问是否可以从p点走到a点。

分析：显然这是一道搜索题，搜索从p到a的路径。在搜索的过程中遇到d生命值减1，遇到k则视为无路径。由于生命值存在0、1、2三种状态，所以不能像走普通的迷宫那样来简单标记某个格子是否可走，而是要用更复杂些的规则来判断一个格子是否需要走：如果曾经有一次以不比当前值低的生命值走过这个这个格子，那么就没有必要再走一次，否则有必要。实现方法是建立一个初始化为0的二维数组，在每次通过某个格子的时候，比较历史走过此格子的最高生命值和当前生命值，如果历史最高生命值不低于当前生命值，则忽略此路径，否则继续此路径。由于本题不要求最短路径，而且可能需要完全的搜索，所以BFS和DFS都可以。

代码如下：
-------------------DFS----------------------
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 40
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;

void input1(){
  int i, j;
  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;
      }
    }
  }
}

int inside(node a){
  return (a.x >= 0 && a.x < size && a.y >= 0 && a.y < size);
}

int dfs1(node cur);

int go1(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(go1(cur, -1, 0))return 1;
  if(go1(cur, 0, -1))return 1;
  if(go1(cur, 1, 0))return 1;
  if(go1(cur, 0, 1))return 1;
  top--;
  return 0;
}

int main(){
  int cases;
  scanf("%d", &cases);
  while(cases--){
    input1();
    node start = {sx, sy, 2};
    if(dfs1(start)){
      printf("Yes\n");
    }else{
      printf("No\n");
    }
  }
  return 0;  
}

----------------------------------------------

---------------------BFS----------------------
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 40
char maze[SIZE][SIZE];
int state[SIZE][SIZE];
typedef struct{
  int x, y, life;
}node ;
int size, sx, sy;

int inside(node a){
  return (a.x >= 0 && a.x < size && a.y >= 0 && a.y < size);
}

void input1(){
  int i, j;
  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;
      }
    }
  }
}

int bfs1(node cur);

int go1(node cur, int dx, int dy){
  node next = cur;
  char t;
  next.x += dx;
  next.y += dy;
  if(!inside(next) || state[next.x][next.y] >= cur.life)return 0;
  t = maze[next.x][next.y];
  if(t == 'd') {
    next.life--;
  }else if(t == 'k'){
    next.life = 0;
  }
  return bfs1(next);
}

int bfs1(node cur){
  if(cur.life <= 0)return 0;
  if(maze[cur.x][cur.y] == 'a')return 1;
  state[cur.x][cur.y] = cur.life;
  if(go1(cur, -1, 0))return 1;
  if(go1(cur, 0, -1))return 1;
  if(go1(cur, 1, 0))return 1;
  if(go1(cur, 0, 1))return 1;
  return 0;
}

int main(){
  int cases;
  scanf("%d", &cases);
  while(cases--){
    input1();
    node start = {sx, sy, 2};
    if(bfs1(start)){
      printf("Yes\n");
    }else{
      printf("No\n");
    }
  }
  return 0;  
}

----------------------------------------------

---

欢迎扫码关注：

转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。