灌溉问题——队列的应用

题目链接：1.灌溉 - 蓝桥云课 (lanqiao.cn)

主要知识点在于队列的使用，详细的解释在代码中注释给出

队列的特性：

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。 

package lanqiao;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * 2023/11/25
 */
public class lanqiao551_灌溉 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//定义四个方向（上、下、左、右）

        public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();//定义花园的长和宽
        int m = scan.nextInt();
        boolean[][] arr = new boolean[n][m];//用来记录方格是否被灌溉过
        Deque<int[]> deque = new ArrayDeque<>();//定义一个队列
        int t = scan.nextInt();//输入水管的数量
        while (t-- > 0)
            deque.add(new int[]{scan.nextInt() - 1, scan.nextInt() - 1});//在队列中加入水管的坐标位置（索引是从0开始的，所以要减1）
        int ans = deque.size();//将ans赋值为队列的大小，ans为方格数
        int k = scan.nextInt();//输入灌溉的分钟数
        int k_=k;//仅是为了最后输出时应用，保留k的初始值
        while (k-- > 0) {
            int size = deque.size();//将队列的大小（此时队列里只有水管处）赋值给size
            for (int i = 0; i < size; i++) {//遍历结束后，队列为空
                //****************
                int[] cur = deque.pollFirst();//取出队列的第一个值（第一次为水管的位置，接下来为已经灌溉过的方块）（取出后队列里就没有这个数字了）
                //****************
                int r = cur[0], c = cur[1];//令r为横坐标（x），c为纵坐标（y）
                for (int[] dir : dirs) {
                    //****************
                    int x = r + dir[0], y = c + dir[1];//将x，y进行上下左右移动，来模仿水的扩展位置

                    if (x >= 0 && x < n && y >= 0 && y < m && !arr[x][y]) {//判断扩展的位置是否合理，而且是否被灌溉过
                        //****************
                        deque.addLast(new int[]{x, y});//如果没有被灌溉过，就把它加入到队列中
                        arr[x][y] = true;//将这个位置置为true，意为已经灌溉过了
                        //****************
                    }
                }
            }
            ans += deque.size();//将每次灌溉好的方块数加入到ans中（每次的队列大小都是重新开始的，都是新增的方块数）
        }
        System.out.println(k_+"分钟后，灌溉的方块数为："+ans);//输出结果
    }
}

其中，while循环中还可以写成：

        while (k-->0){
            int size=deque.size();
            for (int i=0;i<size;i++){
                int[] cur=deque.pollFirst();
                int r=cur[0],c=cur[1];
                for (int j=0;j< 4;j++){//代替上面代码中比较难理解的增强for循环
                    int x=r+dirs[j][0];//与上面代码的解释相同，向四个方向进行判断
                    int y=c+dirs[j][1];
                    if (x<0||x>=n||y<0||y>=m)//与上面代码的判断条件相反，此处为如果超出花园的范围，则跳出此次循环，进行下一个方向的判断
                        continue;
                    if (!arr[x][y]){//如果方块没被灌溉过，则加入到队列，并修改状态为灌溉过
                        deque.addLast(new int[]{x,y});
                        arr[x][y]=true;
                    }
                }
            }

 运行结果：

3 6
2
2 2
3 4
1
1分钟后，灌溉的方块数为：9

进程已结束，退出代码为 0