Jun 16

WOJ1041 MagicForest 解题报告 不指定

felix021 @ 2008-6-16 06:50 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4309) | Via 本站原创 | |
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
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]