队列&栈(Queue&Stack)

队列：先入先出的数据结构

在FIFO数据结构中，将首先处理添加到队列中的第一个元素。

队列的实现

为了实现队列，我们可以使用动态数组和指向队列头部的索引。队列应支持两种操作：入队和出队。入队向队列追加一个元素，而出队会删除第一个元素。

class MyQueue{
    private List<Integer> data;
    private int pStart;
    public MyQueue(){
        data = new ArrayList<Integer>();
        pStart = 0;
    }
    public boolean enQueue(int x){
        data.add(x);
        return true;
    }
    public boolean deQueue(){
        if(isEmpty() == true){
            return false;
        }
        pStart++;
        return true;
    }
    public int front(){
        return data.get(pStart);
    }
    public boolean isEmpty(){
        return pStart >= data.size();
    }
}

上述实现的缺点：随着起始指针的移动，浪费了越来越多的空间，当我们有空间限制时，这将是难以接受的。

循环队列

为了解决上述问题，提供了一种简单但低效的队列实现。具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重用被浪费的存储。

class MyCircularQueue {

    private int[] queue;
    private int index;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        this.queue = new int[k];
        this.index = 0;
        this.capacity = k;
        this.count = 0;

    }
    
    public boolean enQueue(int value) {
        if(count == capacity){
            return false;
        }
        queue[(this.index + this.count) % this.capacity] = value;
        this.count++;
        return true;
    }
    
    public boolean deQueue() {
        if(this.count == 0){
            return false;
        }
        this.index = (this.index + 1) % this.capacity;
        this.count--;
        return true;
    }
    
    public int Front() {
        if(this.count == 0){
            return -1;
        }
        return this.queue[this.index];
    }
    
    public int Rear() {
        if(this.count == 0){
            return -1;
        }
        int tail = (this.index + this.count - 1) % this.capacity;
        return this.queue[tail];
    }
    
    public boolean isEmpty() {
        return this.count == 0;
    }
    
    public boolean isFull() {
        return this.count == this.capacity;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

数据流中的移动平均值

class MovingAverage {

    /** Initialize your data structure here. */
    //窗口的大小
    private int size;
    //窗口中数字的和
    private int windowSum = 0;
    //一共的元素数量
    private int count;
    //双端队列存储
    private Deque<Integer> queue = new ArrayDeque<>();

    public MovingAverage(int size) {
        this.size = size;
    }
    
    public double next(int val) {
        this.count++;
        queue.add(val);
        int tail = count > size ? queue.poll() : 0;
        windowSum = windowSum - tail + val;

        return windowSum * 1.0 / Math.min(size, count);
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

队列和BFS

广度优先搜索(BFS)的一个常见应用是找出根节点到目标节点的最短路径。

结点的处理顺序是：在第一轮中，处理根结点。第二轮中，处理根结点旁边的结点；第三轮中，处理距离根结点两步的结点，等等。

与树的层序遍历类似，越是接近根结点的结点将越早地遍历

在第K轮种将结点X添加到队列中，则根结点与X之间的最短路径长度恰好是K。也就是说，第一次找到目标节点时，你已经处于最短路径中。

队列的入队和出队顺序是什么：首先将根结点排入队列，然后在每一轮中，我们逐个处理已经排在队列中的结点，并将所有的邻居添加到队列中。新添加的结点不会立即遍历，而是在下一轮中处理。

广度优先搜索-模板

BFS的两个主要方案：遍历和找出最短路径。通常，这发生在树或图中。

模板一

int BFS(Node root, Node target){
    Queue<Node> queue;
    int step = 0;
    //initialize
    add root to queue;
    //BFS
    while(queue is not empty){
        step = step + 1;
        int size = queue.size();
        for(int i = 0; i < size; i++){
            Node cur = the first node in queue;
            return step if cur is target;
            for(Node next : the neighbors of cur){
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    
    return -1;
}

模板二

有时，确保我们永远不会访问一个结点两次，否则，可能陷入无限循环。我们可以在上面的代码中添加一个哈希集来解决这问题

int BFS(Node root, Node target){
    Queue<Node> queue;
    Set<Node> used;
    int step = 0;
    //initialize
    add root to queue;
    add root to used;
    //BFS
    while(queue is not empty){
        step = step + 1;
        int size = queue.size();
        for(int i = 0; i < size; i++){
            Node cur = the first node in queue;
            return step if cur is target;
            for(Node next: the neighbors of cur){
                if(next is not in used){
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;
}

墙与门

class Solution {
    public void wallsAndGates(int[][] rooms) {
        //获取行数
        int m = rooms.length;
        if(m == 0){
            return;
        }
        //获取列数
        int n = rooms[0].length;

        //创建一个二维数组，存储移动的方向
        int[][] moves = new int[][]{
            {1, 0},
            {-1, 0},
            {0, -1},
            {0, 1}
        };

        //创建一个队列用于存储遍历的结点
        Deque<int[]> queue = new ArrayDeque<>();
        //遍历rooms将所有的门位置添加到队列中
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(rooms[i][j] == 0){
                    queue.add(new int[]{i, j});
                }
            }
        }

        //BFS
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int row = point[0];
            int col = point[1];
            //遍历当前位置的可移动方向
            for(int[] move : moves){
                int r = row + move[0];
                int c = col + move[1];
                //剪枝，检验位置是否合法
                if(r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != Integer.MAX_VALUE){
                    continue;
                }
                rooms[r][c] = rooms[row][col] + 1;
                //添加新结点
                queue.add(new int[]{r, c});
            }
        }
    }
}

岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        //边界条件
        if(grid == null || grid.length == 0){
            return 0;
        }

        //记录岛屿的个数
        int count = 0;

        //遍历每个格子
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    count++;
                    bfs(grid, i, j);
                }
            }
        }

        return count;
    }

    //bfs
    private void bfs(char[][] grid, int x, int y){
        //首先将该位置置0
        grid[x][y] = '0';

        //创建一个队列保存当前位置
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        //创建一个可移动数组
        int[][] moves = new int[][]{
            {0, -1},
            {0, 1},
            {-1, 0},
            {1, 0}
        };

        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int raw = point[0];
            int col = point[1];
            //遍历可移动的方向
            for(int[] move : moves){
                int r = raw + move[0];
                int c = col + move[1];
                if(r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0'){
                    continue;
                }
                grid[r][c] = '0';
                //添加新结点
                queue.add(new int[]{r, c});
            }
        }
    }
}

打开转盘锁

class Solution {
    public int openLock(String[] deadends, String target) {
        //边界条件
        if("0000".equals(target)){
            return 0;
        }
        //创建一个set保存deadends
        HashSet<String> dead = new HashSet<>();
        //将deaddends存入set
        for(String deads : deadends){
            dead.add(deads);
        }

        if(dead.contains("0000")){
            return -1;
        }

        //记录步骤数
        int step = 0;
        //创建一个队列用于存储下一个遍历的数
        Deque<String> queue = new ArrayDeque<>();
        //创建一个set集合用于记录以遍历过的数
        HashSet<String> used = new HashSet<>();
        queue.add("0000");
        used.add("0000");

        //BFS
        while(!queue.isEmpty()){
            step++;
            //获取队列中的元素个数
            int size = queue.size();
            //遍历这些元素
            for(int i = 0; i < size; i++){
                //获取当前的数
                String cur = queue.poll();
                //遍历这个数可以变化的数
                for(String next : get(cur)){
                    //下一个不在死亡数组中且没有使用过
                    if(!used.contains(next) && !dead.contains(next)){
                        //若下一个数为目标则直接返回
                        if(next.equals(target)){
                            return step;
                        }
                        //否则队列中添加下一个数，且在记录中保存
                        queue.add(next);
                        used.add(next);
                    }
                }
            }
        }

        return -1;
    }

    private List<String> get(String str){
        //创建List
        List<String> res = new ArrayList<>();
        //获取str字符串数组
        char[] ch = str.toCharArray();
        for(int i = 0; i < 4; i++){
            char num = ch[i];
            ch[i] = numjia(num);
            res.add(new String(ch));
            ch[i] = numjian(num);
            res.add(new String(ch));
            ch[i] = num;
        }

        return res;
    }

    private char numjia(char x){
        return x == '9' ? '0' : (char)(x+1);
    }

    private char numjian(char x){
        return x == '0'? '9' : (char)(x-1);
    }
}

完全平方数

class Solution {
    public int numSquares(int n) {
        //创建一个队列用于bfs
        Deque<Integer> queue = new ArrayDeque<>();
        //创建一个set用于记录访问过数
        Set<Integer> set = new HashSet<>();
        queue.add(0);
        set.add(0);
        //记录数的个数
        int count = 0;

        //bfs
        while(!queue.isEmpty()){
            count++;
            //记录当前队列中的元素的个数
            int size = queue.size();
            //遍历当前队列中的元素
            for(int i = 0; i < size; i++){
                //取出队列中的数
                int cur = queue.poll();
                //遍历下一个可能的数
                for(int j = 1; j * j + cur <= n; j++){
                    int next = cur + j * j;
                    //next为目标则直接返回
                    if(next == n){
                        return count;
                    }
                    if(next < n && !set.contains(next)){
                        queue.add(next);
                        set.add(next);
                    }
                }
            }
        }

        return -1;
    }
}

后入先出的数据结构

在LIFO数据结构中，将首先处理添加到队列中的最新元素。与队列不同，栈是一个LIFO数据结构。通常，插入操作在栈中被称作入栈push。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈pop，将始终删除队列中相对于它的最后一个元素。

栈的实现

class MyStack{
    private List<Integer> data;
    
    public MyStack(){
        data = new ArrayList<>();
    }
    public void push(int x){
        data.add(x);
    }
    public boolean isEmpty(){
        return data.isEmpty();
    }
    public int top(){
        return data.get(data.size() - 1);
    }
    public boolean pop(){
        if(isEmpty()){
            return false;
        }
        data.remove(data.size()-1);
        return true;
    }
}

最小栈

class MinStack {

    /** initialize your data structure here. */
    class Node{

        private int val;
        private int min;
        private Node next;
        public Node(int val, int min, Node next){
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }

    private Node head;

    public MinStack() {

    }
    
    public void push(int val) {
        if(head == null){
            head = new Node(val, val, null);
        }else{
            head = new Node(val, Math.min(head.min, val), head);
        }
    }
    
    public void pop() {
        if(head == null){
            throw new IllegalStateException("error");
        }else{
            Node temp = head;
            head = head.next;
            temp.next = null;
            temp = null;
        }
    }
    
    public int top() {
        if(head == null){
            throw new IllegalStateException("error");
        }else{
            return head.val;
        }
    }
    
    public int getMin() {
        if(head == null){
            throw new IllegalStateException("error");
        }else{
            return head.min;
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

有效括号

class Solution {
    public boolean isValid(String s) {
        //创建一个栈来存放字符
        Deque<Character> stack = new ArrayDeque<>();
        //遍历字符串数组
        for(char ch : s.toCharArray()){
            if(ch == '('){
                 stack.push(')');
            }else if(ch == '['){
                stack.push(']');
            }else if(ch == '{'){
                stack.push('}');
            }else{
                if(stack.isEmpty() || ch != stack.pop()){
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        //创建一个栈来存放其中的元素
        Deque<Integer> stack = new ArrayDeque<>();
        //创建一个数组用于存放结果
        int[] res = new int[temperatures.length];

        //遍历数组
        for(int i = 0; i < temperatures.length; i++){
            //当栈中不为空且当前元素大于栈顶元素时出栈
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }

        return res;
    }
}

逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        //创建一个栈用于存储数值
        Deque<Integer> stack = new ArrayDeque<>();
        //遍历字符串数组
        for(String str : tokens){
            //若遍历的为运算符则弹出两个数组进行运算并压入
            if("+".equals(str)){
                //首先弹出的为后面的数字
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 + num2);
            }else if("-".equals(str)){
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 - num2);
            }else if("*".equals(str)){
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 * num2);
            }else if("/".equals(str)){
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(num1 / num2);
            }else{
                //若为数字，则直接压入
                stack.push(Integer.parseInt(str));
            }
        }

        return stack.pop();
    }
}

栈和深度优先搜索

与BFS类似，深度优先搜索是用于在树/图中遍历/搜索的另外一种重要算法。也可以在更抽象的场景中使用。

正如树的遍历中所提到的，我们可以用DFS进行前序遍历，中序遍历，后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯。

DFS和BFS最大的区别，BFS永远不会深入搜索，除非它已经在当前层级访问了所有结点。

通常，我们使用递归实现DFS。栈在递归中起着重要的作用。

DFS-模板

在大多数情况下，我们在能使用BFS时也可以使用DFS。但是有一个重要的区别：遍历顺序。

与BFS不同，更早访问的结点可能不是更靠近根结点的结点。因此，在DFS中找到的第一条路径可能不是最短路径。

模板-递归

boolean DFS(Node cur, Node target, Set<Node> visited){
    return if cur is target;
    for(next : each neighbor of cur){
        if(next is not in visited){
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
}

岛屿数量

class Solution {
    public int numIslands(char[][] grid) {
        //边界条件
        if(grid == null || grid.length == 0){
            return 0;
        }

        //创建一个岛屿计数
        int count = 0;

        //遍历二维数组
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    //dfs
    private void dfs(char[][] grid, int i, int j){
        //检查边界条件
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1'){
            return;
        }
        //将当前位置的值修改为0
        grid[i][j] = '0';
        //dfs上下左右
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
}

克隆图

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        return clone(node, new HashMap<>());
    }

    private Node clone(Node node, Map<Integer, Node> used){
        //边界条件
        if(node == null){
            return node;
        }

        //判断当前是否被访问过
        if(used.containsKey(node.val)){
            return used.get(node.val);
        }

        //创建新结点
        Node newNode = new Node(node.val, new ArrayList<>());
        //将当前结点放入used中
        used.put(newNode.val, newNode);

        //访问node结点的邻居节点
        for(Node next : node.neighbors){
            newNode.neighbors.add(clone(next, used));
        }

        return newNode;
    }
}

目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    private int dfs(int[] nums, int target, int index, int sum){
        //递归出口
        if(index == nums.length){
            return sum == target ? 1 : 0;
        }

        return dfs(nums, target, index+1, sum+nums[index]) + 
        dfs(nums, target, index+1, sum-nums[index]);
    }
}

DFS-模板II

boolean DFS(int root, int target){
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while(s is not empty){
        Node cur = the top element in s;
        return true if cur is target;
        for(Node next : the neighbors of cur){
            if(next is not in visited){
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //创建list用于存储结果
        List<Integer> res = new ArrayList<>();
        //边界条件
        if(root == null){
            return res;
        }
        //创建一个栈用来存储结点
        Deque<TreeNode> stack = new ArrayDeque<>();

        //DFS
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //弹出一个结点
            TreeNode node = stack.pop();
            //访问该结点
            res.add(node.val);
            //访问右子节点
            root = node.right;
        }

        return res;
    }
}

用栈实现队列

class MyQueue {

    /** Initialize your data structure here. */
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        return stack2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }

        return stack2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

用队列实现栈

class MyStack {

    /** Initialize your data structure here. */

    private Deque<Integer> queue1;
    private Deque<Integer> queue2;

    public MyStack() {

        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        //将队列1中的元素加入队列2中
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        //交换两个队列
        Deque<Integer> temp = queue2;
        queue2 = queue1;
        queue1 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

字符串解码

class Solution {
    public String decodeString(String s) {
        //定义一个num用来保存读取的数据
        int num = 0;
        //创建一个StirngBuilder用于保存结果
        StringBuilder res = new StringBuilder();
        //创建一个栈用于记录num
        Deque<Integer> numStack = new ArrayDeque<>();
        //创建一个栈用于记录当前结果
        Deque<StringBuilder> resStack = new ArrayDeque<>();

        //遍历字符数组
        for(char ch : s.toCharArray()){
            //若字符为数字,则记录数字
            if(Character.isDigit(ch)){
                num = num * 10 + (ch - '0');
            }else if(ch == '['){
                //若字符为[，则在栈中压入当前的res和num
                numStack.push(num);
                resStack.push(res);
                //重置num和res
                num = 0;
                res = new StringBuilder();
            }else if(ch == ']'){
                //若字符为],则弹出res栈中的结果和num栈中的数字
                StringBuilder pre = resStack.pop();
                int n = numStack.pop();
                //repeat
                for(int i = 0; i < n; i++){
                    pre.append(res);
                }
                res = pre;
            }else{
                //若为字母则直接添加
                res.append(ch);
            }
        }

        return res.toString();
    }
}

图像渲染

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        //记录旧的颜色
        int oldColor = image[sr][sc];
        //判断是否需要渲染
        if(oldColor != newColor){
            dfs(image, sr, sc, newColor, oldColor);
        }

        return image;
    }

    //dfs
    private void dfs(int[][] image, int i, int j, int newColor, int oldColor){
        //位置合法性判断
        if(i >= 0 && j >= 0 && i < image.length && j < image[0].length && image[i][j] == oldColor){
            //渲染当前位置
            image[i][j] = newColor;
            //四个方向进行dfs
            dfs(image, i+1, j, newColor, oldColor);
            dfs(image, i-1, j, newColor, oldColor);
            dfs(image, i, j+1, newColor, oldColor);
            dfs(image, i, j-1, newColor, oldColor);
        }
    }
}

01矩阵

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        //创建一个二维数组用于保存res
        int[][] res = new int[mat.length][mat[0].length];
        //创建一个二维数组用于记录是否以访问
        boolean[][] used = new boolean[mat.length][mat[0].length];
        //创建一个队列用于bfs
        Deque<int[]> queue = new ArrayDeque<>();

        //遍历数组，将值为0的坐标入队
        for(int i = 0; i < mat.length; i++){
            for(int j = 0; j < mat[0].length; j++){
                if(mat[i][j] == 0){
                    queue.offer(new int[]{i, j});
                    used[i][j] = true;
                }
            }
        }

        //构建一个方向数组
        int[][] moved = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
        };

        //bfs
        while(!queue.isEmpty()){
            //出队获取坐标位置
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            //遍历当前点可移动的方向
            for(int[] move : moved){
                int nx = x + move[0];
                int ny = y + move[1];
                //坐标位置合法性检查
                if(nx >= 0 && ny >= 0 && nx < mat.length && ny < mat[0].length && !used[nx][ny]){
                    //新的位置值的值为旧的+1，并加入队列和used中
                    res[nx][ny] = res[x][y] + 1;
                    queue.offer(new int[]{nx, ny});
                    used[nx][ny] = true;
                }
            }
        }

        return res;
    }
}