乳草的侵占
Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植物大战人类中败下阵来，邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。
草地像往常一样，被分割成一个高度为Y(1 <= y <= 100),宽度为X(1 <= x <= 100)的直角网格。(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。乳草一开始占领了格(Mx,My)。每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格（包括垂直与水平相邻的和对角线上相邻的格）。1周之后，这些新占领的格又可以把乳草传播到更多的格里面了。
Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(Mx,My)，那么还在那个时刻它们可以完全占领入侵整片草地呢（对给定的数据总是会发生）？
草地由一个图片表示。" ." 表示草，而" *" 表示大石。
比如这个X=4,Y=3的例子。
....
..*.
.**.
如果乳草一开始在左下角（第1排，第1列），那么草地的地图将会以如下态势发展：
.... .... MMM. MMMM MMMM
..*. MM*. MM*. MM*M MM*M
M**. M**. M**. M**. M**M
星期数 0 1 2 3 4
乳草会在4星期后占领整片土地。
输入格式：
第一行：四个由空格隔开的整数: X, Y, Mx, My
第 2 到第Y + 1行：数据的第y + 1行由X个字符（" ." 表示草地，" *" 表示大石），描述草地的第(Y + 2 - y)行。
输出格式：
一个单独的整数表示最后一个不是大石块的格子被乳草占领的星期数。
样例输入
4 3 1 1
....
..*.
.**.
样例输出
4
思路：
首先一上来感觉很简单，用BFS一层一层的搜，最后一个出队列的肯定是就是答案。这么想的确没错。但是一测试就是错的。。。。
题目挖了个坑给人跳，题目描述的是几何坐标，而且范围在几何坐标的右上角，原点(0, 0)在左下角，而数组的起始点是在左上角，这里需要进行转换。
怎么转换呢？
1、先把读到的宽度X和高度Y转换为数组的行数row和列数col
X ==> row Y ==> col
2、把题目给的乳草初始占领点（Mx，My）转换为数组的坐标形式
数组的行数为row，几何坐标转数组坐标：（x, y）-> (row - (y+1)，x)
乳草初始占领点(Mx, My)是几何坐标
设数组对应的坐标为(x1, y1)，数组的行数为row
则：
x1 = row - My - 1
y1 = Mx
解决了这个坑，后面的就简单多了。
把起始点Node = new first(x1, y1, 0)放入队列，然后根据first的坐标进行八个方向的搜索（这里Node的坐标是表示该点在数组中的坐标）。
当队列最后一个Node出来后，该Node就是最后一个被感染的草地。
代码：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* 乳草的侵占
* @author 无处安身
*
*/
public class Main {
static class Node{
int x;
int y;
int step = 0; // 表示这个点在第几周被感染了
public Node(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int X, Y, Mx, My;
X = sc.nextInt(); // 宽度 —— x坐标
Y = sc.nextInt(); // 高度 —— y坐标
Mx = sc.nextInt() - 1;
My = sc.nextInt() - 1;
My = Y - My - 1;
// 将获取到的宽度 X 和高度 Y转换为数组的行和列
int row = Y; // 行
int col = X; // 列
char[][] map = new char[row+5][col+5];
for (int i = 0; i < row; i++) {
String str = sc.next();
map[i] = str.toCharArray();
}
int[][] vis = new int[row + 5][col + 5];
// 方向数组
int[][] dir = {
{-1, 0}, // 上
{-1, 1}, // 右上
{0, 1}, // 右
{1, 1}, // 右下
{1, 0}, // 下
{1, -1}, // 左下
{0, -1}, // 左
{-1, -1} // 左上
};
Queue<Node> q = new LinkedList<Node>();
/**
* 几何坐标转数组坐标
* 乳草初始占领点(Mx, My)是几何坐标
* 设数组对应的坐标为(x1, y1)，数组的行数为row
* 则：
* x1 = row - My - 1
* y1 = Mx
*/
int x1 = row - My - 1;
int y1 = Mx;
Node first = new Node(x1, y1, 0);
q.add(first);
Node now = first;
vis[x1][y1] = 1;
while(!q.isEmpty()) {
now = q.poll();
for (int i = 0; i < 8; i++) {
int tx = now.x + dir[i][0];
int ty = now.y + dir[i][1];
if(tx >= 0 && tx < row && ty >= 0 && ty < col && vis[tx][ty] == 0 && map[tx][ty] == '.') {
vis[tx][ty] = 1;
int step = now.step + 1;
q.add(new Node(tx, ty, step));
}
}
}
System.out.println(now.step);
}
}
网友评论