Pilot's Blog
0%

BFS - 灌溉

发表于 更新于 分类于 ， ， Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟
虽说是模拟题，但是用BFS不是更香吗

题目

输入

1
2
3
4
5
3 6
2
2 2
3 4
1

输出

1
9

分析

多源BFS的思路

定义一个节点类，记录这个节点的x坐标，y坐标和这个节点的“层数”（放在这道题里面其实就是第几分钟灌溉好的）

定义一个辅助二维数组，记录当前节点是否访问过

每轮循环先访问队列中队首节点，如果当前队首节点的层数小于等于时间，说明可以继续，按上下左右顺序访问当前弹出的节点的临近节点，如果临近节点之前没有访问过，就压入队列并且设为访问过

Java中队列操作

声明

1
2
3
import java.util.Queue;
import java.util.LinkedList;
Queue<Node> queue = new LinkedList<>();

加入元素

1
queue.add(Node);

访问队首元素

1
Node node = queue.peek()

弹出队首元素

1
queue.poll()

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
// 1:无需package
// 2: 类名必须Main, 不可修改
class Node {
	int x;
	int y;
	int floor;
	public Node(int x, int y, int floor) {
		this.x = x;
		this.y = y;
		this.floor = floor;
	}
}
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n = scan.nextInt();
        int m = scan.nextInt();
        int t = scan.nextInt();
        boolean[][] graph = new boolean[n + 1][m + 1];
        Queue<Node> queue = new LinkedList<>();
        for(int i = 0; i < t; i++) {
        	int x = scan.nextInt();
        	int y = scan.nextInt();
        	Node newNode = new Node(x, y, 1);
        	queue.add(newNode);
        	graph[x][y] = true;
        }
        int k = scan.nextInt();
        int count = t;
        while(!queue.isEmpty()) {
        	Node newNode = queue.peek();
        	if(newNode.floor <= k) {
            	queue.poll();
            	int centerX = newNode.x;
            	int centerY = newNode.y;
            	//向上的方向
            	if(centerX - 1 >= 1 && graph[centerX - 1][centerY] == false) {
            		graph[centerX - 1][centerY] = true;
            		queue.add(new Node(centerX - 1, centerY, newNode.floor + 1));
            		count++;
            	}
            	//向下的方向
            	if(centerX + 1 <= n && graph[centerX + 1][centerY] == false) {
            		graph[centerX + 1][centerY] = true;
            		queue.add(new Node(centerX + 1, centerY, newNode.floor + 1));
            		count++;
            	}
            	//向左
            	if(centerY - 1 >= 1 && graph[centerX][centerY -1 ] == false) {
            		graph[centerX][centerY - 1] = true;
            		queue.add(new Node(centerX, centerY - 1, newNode.floor + 1));
            		count++;
            	}
            	//向右
            	if(centerY + 1 <= m && graph[centerX][centerY + 1] == false) {
            		graph[centerX][centerY + 1] = true;
            		queue.add(new Node(centerX, centerY + 1, newNode.floor + 1));
            		count++;
            	}
        		
        	} else {
        		break;
        	}
        }
        System.out.print(count);
        scan.close();
    }
}