January 31, 2022: Maze III. There is a ball in the maze of open spaces and walls. ball

2022-01-31： maze III.

There is a ball in the maze of open spaces and walls . The ball can go up （u） Next （d） Left （l） Right （r） Scroll in four directions , But it doesn't stop rolling until it hits a wall . When the ball stops , You can select the next direction . There is also a hole in the maze , When the ball moves through the hole , Will fall into the hole .

Given the starting position of the ball , Destination and maze , Find the path to let the ball fall into the hole at the shortest distance . The definition of distance is that the ball starts from its starting position （ barring ） Destination （ Include ） The number of open spaces passed . adopt 'u', 'd', 'l' and 'r' Output the moving direction of the ball . Since there may be multiple shortest paths , Please output the path with the smallest dictionary order . If the ball doesn't get into the hole , Output "impossible".

The maze consists of a 0 and 1 Two dimensional array representation of . 1 Wall ,0 Representing vacant land . You can assume that the edges of the maze are all walls . The coordinates of the starting position and destination are given by row number and column number .

Power button 499.

answer 2022-01-31：

Breadth first traversal . Every step , All need to be recorded .

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    maze := [][]int{
        {0, 0, 0, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1},
        {0, 1, 0, 0, 0},
    }
    ball := []int{4, 3}
    hole := []int{0, 1}
    ret := findShortestWay(maze, ball, hole)
    fmt.Println(ret)
}

//  node ： Where have you come ？(r,c) This position 
//  From which direction ！d -> 0 1 2 3 4
//  What decision did you make before you came to this position .
type Node struct {
    r int
    c int
    d int
    p string
}

func NewNode(row, col, dir0 int, path0 string) *Node {
    ans := &Node{}
    ans.r = row
    ans.c = col
    ans.d = dir0
    ans.p = path0
    return ans
}

func findShortestWay(maze [][]int, ball, hole []int) string {
    n := len(maze)
    m := len(maze[0])
    q1 := make([]*Node, n*m)
    q2 := make([]*Node, n*m)
    s1 := 0
    s2 := 0
    visited := make([][][]bool, len(maze))
    for i := 0; i < len(maze); i++ {
        visited[i] = make([][]bool, len(maze[0]))
        for j := 0; j < len(maze[0]); j++ {
            visited[i][j] = make([]bool, 4)
        }
    }
    s1 = spread(maze, n, m, NewNode(ball[0], ball[1], 4, ""), visited, q1, s1)
    for s1 != 0 {
        for i := 0; i < s1; i++ {
            cur := q1[i]
            if hole[0] == cur.r && hole[1] == cur.c {
                return cur.p
            }
            s2 = spread(maze, n, m, cur, visited, q2, s2)
        }
        tmp := q1
        q1 = q2
        q2 = tmp
        s1 = s2
        s2 = 0
    }
    return "impossible"
}

var to = [][]int{{1, 0}, {0, -1}, {0, 1}, {-1, 0}, {0, 0}}

var re = []string{"d", "l", "r", "u"}

// maze maze , Go to the grid 
// n  Row number 
// m  Number of columns 
//  The current node ,cur -> (r,c)  Direction   route （ decision ）
// v [ That's ok ][ Column ][ Direction ]  A grid , In fact, in the case of finite width traversal , yes 4 A little bit ！
// q  The next level of queues 
// s  Where is the next level of queue filled ,size
//  Current point cur, The split split split , It's time to keep going , The resulting point of a lower layer , Get into q,s++
//  Return value ：q Where has it grown ？ return size -> s
func spread(maze [][]int, n, m int, cur *Node, v [][][]bool, q []*Node, s int) int {
    d := cur.d
    r := cur.r + to[d][0]
    c := cur.c + to[d][1]
    //  Cleavage ！
    if d == 4 || r < 0 || r == n || c < 0 || c == m || maze[r][c] != 0 {
        for i := 0; i < 4; i++ {
            if i != d {
                r = cur.r + to[i][0]
                c = cur.c + to[i][1]
                if r >= 0 && r < n && c >= 0 && c < m && maze[r][c] == 0 && !v[r][c][i] {
                    v[r][c][i] = true
                    next := NewNode(r, c, i, cur.p+re[i])
                    q[s] = next
                    s++
                }
            }
        }
    } else { //  Not split ！ Continue to go ！
        if !v[r][c][d] {
            v[r][c][d] = true
            q[s] = NewNode(r, c, d, cur.p)
            s++
        }
    }
    return s
}

The results are as follows ：

picture

Zuo Shen java Code