题意描述:
一个房间上有红色的瓦和黑色的瓦片,给出红瓦和黑瓦的位置和人所占的位置,求人最多能走过多少片瓦?
(条件为:人行走过程中只能走黑瓦,且人的初始位置为黑瓦)
输入描述:输入的字符里面只有三种字符:
“@”-----表示人(只能有一个该字符)
“.”-----表示黑瓦
“#”-----表示红瓦
样例:
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
本文主要探讨了两种基础的搜索算法——深度优先搜索(DFS)和宽度优先搜索(BFS),以及剪枝策略,并通过POJ平台上的实例进行了分析。 1. **搜索算法基本概念** - **状态(state)**:表示问题在某个时间点的进展...
描述中提到的“叉积+深搜”,指的是在解决这个问题时可能用到的两种技术。叉积是向量运算的一种,用于判断两个向量的方向关系,也可以用来计算两个向量构成的角的大小。在计算几何中,叉积常用于判断点的位置关系、...
《POJ1184-Smart typist:深入解析搜索与状态压缩算法》 在编程竞赛的世界里,POJ1184是一个经典的题目,它挑战了程序员对搜索算法和状态压缩技术的理解与应用。本篇文章将围绕这个题目,详细阐述其背后的算法思想...
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
【北大POJ初级-简单搜索】是北京大学在线判题系统POJ(Problem Online Judge)针对初学者设置的一类编程题目,主要涉及基础的算法和数据结构应用。这类问题通常不会过于复杂,旨在帮助学习者掌握基本的编程思维和...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
【标题】"poj1276解答和分析"是一个关于解决特定编程问题的资源集合,其中包含了作者对于这个问题的理解、解析以及相应的源代码。在编程竞赛或算法学习中,POJ(Problem On The Internet)是流行的一个在线判题系统...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
简单搜索题 数独 答案 POJ 2676 也可以没事玩玩数独。
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
POJ1852题目详解 POJ1852题目是一道关于计算最早和最晚可能时间的题目,问题描述如下:有一根长度为L厘米的水平竿,每个蚂蚁以1厘米/秒的速度移动。当蚂蚁走到竿子的一端时,它会立刻掉下去。当两个蚂蚁相遇时,...
这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165道题目,涵盖了多种算法和数据结构的学习与实践。 ### 初级阶段训练计划 #### 第1周至第2周(共80题) - **基础算法** - 枚举:通过列举所有可能的情况...
标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...
- **解释**:队列和栈是两种常见的线性数据结构,用于存储和管理数据元素。 #### 5. Trie树 - **例题**:poj2513 - **解释**:Trie树(字典树)是一种用于存储和检索字符串的高效数据结构。 ### 三、动态规划 ###...
POJ题目分析与理解 POJ(Peking University Online Judge)是一款在线评测系统,旨在帮助程序员提高编程能力和解决问题的能力。该系统提供了大量的编程题目,涵盖了算法、数据结构、数学、动态规划、博弈论等多个...