讨论/题目交流/🏆 迎国庆,力扣第 156 场周赛 🇨🇳/
🏆 迎国庆,力扣第 156 场周赛 🇨🇳

祖国 image.png 周年盛世华诞,这是国庆前的一场激烈竞赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验,祝大家国庆假期快乐。

image.png前往竞赛本周周赛题目:

独一无二的出现次数
尽可能使字符串相等
删除字符串中的所有相邻重复项 II
穿过迷宫的最少移动次数 —— 小蛇移动

展开讨论

求助各位大佬帮忙看一下为什么第四题的case会有不通过?不通过的case在main函数中定义了。
超级感谢!!!

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.*;

class Solution {

    public static void main(String[] args) {
        int[][] grid = new int[][] {
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,1,1,0,0,1,0,0,0},
                {0,0,1,0,0,0,0,0,0,0},
                {1,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,0,0,0,1,0},
                {0,0,0,0,0,0,1,0,0,1},
                {0,1,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,1,0,0,0,0}

        };
        System.out.println(new Solution().minimumMoves(grid));
    }

    public int minimumMoves(int[][] grid) {
        // 这个就是动态规划了,
        int rowNum = grid.length;
        int colNum = grid[0].length;
        if (grid[rowNum-1][colNum-2]==1 || grid[rowNum-1][colNum-1]==1)
            return -1;
        int[][][] pos = new int[rowNum][colNum][2]; // 第三维度0表示向右横着,1表示向下竖着
        // 用广度优先BFS,只要遍历到,就是最短
        Stack<State> stack = new Stack<>();
        stack.push(new State(0, 0, 0));
        pos[0][0][0] = 1; // 标记初始位置。因为0表示未被访问过。
        while(!stack.isEmpty()) {
            int len = stack.size();
            for (int i=0; i<len; i++) {
                State s = stack.pop();
                // 判断当前方向
                if (s.dir==0) { // 如果是横向向右
                    // 1. 变向
                    if (s.row<rowNum-1 && pos[s.row][s.col][1]==0 && grid[s.row+1][s.col]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col][1] = pos[s.row][s.col][0]+1;
                        stack.push(new State(s.row, s.col, 1));
                    }
                    // 2. 右行
                    if (s.col<colNum-2 && pos[s.row][s.col+1][0]==0 && grid[s.row][s.col+2]==0) {
                        pos[s.row][s.col+1][0] = pos[s.row][s.col][0]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row, s.col+1, 0));
                    }
                    // 3. 下行
                    if (s.row<rowNum-1 && pos[s.row+1][s.col][0]==0 && grid[s.row+1][s.col]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row+1][s.col][0] = pos[s.row][s.col][0]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row+1, s.col, 0));
                    }

                } else { // 如果是纵向向下
                    // 1. 变向
                    if (s.col<colNum-1 && pos[s.row][s.col][0]==0 && grid[s.row][s.col+1]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col][0] = pos[s.row][s.col][1]+1;
                        if (pos[rowNum-1][colNum-2][0]!=0) {
                            return pos[rowNum-1][colNum-2][0]-1;
                        }
                        stack.push(new State(s.row, s.col, 0));
                    }
                    // 2. 右行
                    if (s.col<colNum-1 && pos[s.row][s.col+1][1]==0 && grid[s.row][s.col+1]==0 && grid[s.row+1][s.col+1]==0) {
                        pos[s.row][s.col+1][1] = pos[s.row][s.col][1]+1;
                        stack.push(new State(s.row, s.col+1, 1));
                    }
                    // 3. 下行
                    if (s.row<rowNum-2 && pos[s.row+1][s.col][1]==0 && grid[s.row+2][s.col]==0) {
                        pos[s.row+1][s.col][1] = pos[s.row][s.col][1]+1;
                        stack.push(new State(s.row+1, s.col, 1));
                    }
                }
            }
        }


        if (pos[rowNum-1][colNum-2][0]==0)
            return -1;
        else
            return pos[rowNum-1][colNum-2][0]-1;
    }


}

  class State {
      int row;
      int col;
      int dir;
      public State(int r, int c, int d) {
          row = r;
          col = c;
          dir = d;
      }
  }
展开全部 21 讨论