`
128kj
  • 浏览: 601384 次
  • 来自: ...
社区版块
存档分类
最新评论

POJ 1979 Red and Black(广搜与深搜两种解答)

阅读更多
题意描述:
   一个房间上有红色的瓦和黑色的瓦片,给出红瓦和黑瓦的位置和人所占的位置,求人最多能走过多少片瓦?
(条件为:人行走过程中只能走黑瓦,且人的初始位置为黑瓦)
输入描述:输入的字符里面只有三种字符:
           “@”-----表示人(只能有一个该字符)
           “.”-----表示黑瓦
           “#”-----表示红瓦

样例:
Sample Input

6  9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

Sample Output

45

AC代码:
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;

class node{  
    int x, y; 
   public node(){
     this(0,0);
   } 
   public node(int x,int y){
     this.x=x;
     this.y=y;
   }
}  
public class Main{
   char room[][];  
   int w, h;  
   int dir[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  
   int ans;

   public Main(int w,int h,char[][] room){
      this.w=w;
      this.h=h;
      this.room=room;
   }
   
   public int getAns(){
      return ans;
   }

   public static void main(String args[]){  
    Scanner in=new Scanner(System.in);
    int sx=0;
    int sy=0;  
   
    while(true){ 
       int w=in.nextInt();
       int h=in.nextInt();
        
       if(0 == w && 0 == h)  
            break;  
        char room[][]=new char[h][w];
       for(int i = 0; i < h; i++){  
          String s=in.next();        
            for(int j = 0; j < w; j++){  
              room[i][j]=s.charAt(j);  
                if(room[i][j] == '@')  
                {  
                    sx = i; sy = j;  
                }  
            }  
        } 
         Main m=new Main(w,h,room); 
       // System.out.printf("%d\n", m.bfs(sx, sy));  //广搜
         m.dfs(sx, sy);
        System.out.printf("%d\n", m.getAns());  
      
    }  
 }  
  
  private int bfs(int x, int y){  
   Queue<node> que=new LinkedList<node>();  
    node t=new node(x,y);
    node tmp=new node();  

    room[x][y] = '#';  //标记为红瓦
    que.offer(t);  
    int nu = 1;  
    while(!que.isEmpty())  
    {  
       tmp = que.poll();  //当前点
       for(int i = 0; i < 4; i++){//当前点的所有邻接点
            int x1 = tmp.x + dir[i][0];  
            int y1 = tmp.y + dir[i][1];  
 
            if(x1 >= 0 && x1 < h &&y1 >= 0 && y1 < w && room[x1][y1] == '.'){  
                
                room[x1][y1] = '#';  //标记为红瓦
                que.offer(new node(x1,y1));  //邻接点入队列
                nu++;  
            }  
        }  
    }  
    return nu;  
  }

   private void dfs(int x, int y){  
    int dx, dy;  
    if(room[x][y] == '#')  
        return;  
    room[x][y] = '#';  
    ans++;  
    for(int i = 0; i < 4; i++)  
    {  
        dx = x + dir[i][0];  
        dy = y + dir[i][1];  
        if(dx >= 0 && dx < h && dy >= 0 && dy < w)  
            dfs(dx, dy);  
    } 
   
  }  
 }
分享到:
评论

相关推荐

    poj 3715 Blue and Red.md

    poj 3715 Blue and Red.md

    深搜宽搜与剪枝分析与poj具体程序举例

    本文主要探讨了两种基础的搜索算法——深度优先搜索(DFS)和宽度优先搜索(BFS),以及剪枝策略,并通过POJ平台上的实例进行了分析。 1. **搜索算法基本概念** - **状态(state)**:表示问题在某个时间点的进展...

    极角排序:POJ 1696(叉积+深搜)

    描述中提到的“叉积+深搜”,指的是在解决这个问题时可能用到的两种技术。叉积是向量运算的一种,用于判断两个向量的方向关系,也可以用来计算两个向量构成的角的大小。在计算几何中,叉积常用于判断点的位置关系、...

    POJ1184-Smart typist【搜索与状态压缩】

    《POJ1184-Smart typist:深入解析搜索与状态压缩算法》 在编程竞赛的世界里,POJ1184是一个经典的题目,它挑战了程序员对搜索算法和状态压缩技术的理解与应用。本篇文章将围绕这个题目,详细阐述其背后的算法思想...

    深搜+宽搜+剪枝 配合POJ题目

    各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。

    北大POJ初级-简单搜索

    【北大POJ初级-简单搜索】是北京大学在线判题系统POJ(Problem Online Judge)针对初学者设置的一类编程题目,主要涉及基础的算法和数据结构应用。这类问题通常不会过于复杂,旨在帮助学习者掌握基本的编程思维和...

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    POJ1503解答,正确答案(已通过POJ)

    POJ1503解答 POJ1503解答,正确答案(已通过POJ)

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    poj1276解答和分析

    【标题】"poj1276解答和分析"是一个关于解决特定编程问题的资源集合,其中包含了作者对于这个问题的理解、解析以及相应的源代码。在编程竞赛或算法学习中,POJ(Problem On The Internet)是流行的一个在线判题系统...

    poj题目分类

    * 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...

    POJ 2676 代码 搜索数独答案

    简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1852题目和详细解答

    POJ1852题目详解 POJ1852题目是一道关于计算最早和最晚可能时间的题目,问题描述如下:有一根长度为L厘米的水平竿,每个蚂蚁以1厘米/秒的速度移动。当蚂蚁走到竿子的一端时,它会立刻掉下去。当两个蚂蚁相遇时,...

    poj训练计划.doc

    这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165道题目,涵盖了多种算法和数据结构的学习与实践。 ### 初级阶段训练计划 #### 第1周至第2周(共80题) - **基础算法** - 枚举:通过列举所有可能的情况...

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **解释**:队列和栈是两种常见的线性数据结构,用于存储和管理数据元素。 #### 5. Trie树 - **例题**:poj2513 - **解释**:Trie树(字典树)是一种用于存储和检索字符串的高效数据结构。 ### 三、动态规划 ###...

    POJ题目分析与理解

    POJ题目分析与理解 POJ(Peking University Online Judge)是一款在线评测系统,旨在帮助程序员提高编程能力和解决问题的能力。该系统提供了大量的编程题目,涵盖了算法、数据结构、数学、动态规划、博弈论等多个...

Global site tag (gtag.js) - Google Analytics