Formatted question description: https://leetcode.ca/all/1730.html

1730. Shortest Path to Get Food

Level

Medium

Description

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an m x n character matrix, grid, of these different types of cells:

'*' is your location. There is exactly one '*' cell.
'#' is a food cell. There may be multiple food cells.
'O' is free space, and you can travel through these cells.
'X' is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

Example 1:

Image text

Input: grid = [[“X”,”X”,”X”,”X”,”X”,”X”],[“X”,”*”,”O”,”O”,”O”,”X”],[“X”,”O”,”O”,”#”,”O”,”X”],[“X”,”X”,”X”,”X”,”X”,”X”]]

Output: 3

Explanation: It takes 3 steps to reach the food.

Example 2:

Image text

Input: grid = [[“X”,”X”,”X”,”X”,”X”],[“X”,”*”,”X”,”O”,”X”],[“X”,”O”,”X”,”#”,”X”],[“X”,”X”,”X”,”X”,”X”]]

Output: -1

Explanation: It is not possible to reach the food.

Example 3:

Image text

Input: grid = [[“X”,”X”,”X”,”X”,”X”,”X”,”X”,”X”],[“X”,”*”,”O”,”X”,”O”,”#”,”O”,”X”],[“X”,”O”,”O”,”X”,”O”,”O”,”X”,”X”],[“X”,”O”,”O”,”O”,”O”,”#”,”O”,”X”],[“X”,”X”,”X”,”X”,”X”,”X”,”X”,”X”]]

Output: 6

Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Example 4:

Input: grid = [[“O”,”*”],[”#”,”O”]]

Output: 2

Example 5:

Input: grid = [[“X”,”*”],[”#”,”X”]]

Output: -1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[row][col] is '*', 'X', 'O', or '#'.
The grid contains exactly one '*'.

Solution

Find the position of '*' cell, and do breadth first search starting from the '*' cell. The visited cells and the obstacles cannot be visited. Once a food cell is met, return the number of steps. If no food cell is met, return -1.

class Solution {
    public int getFood(char[][] grid) {
        int rows = grid.length, columns = grid[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int startRow = -1, startColumn = -1;
        int total = rows * columns;
        for (int i = 0; i < total; i++) {
            int row = i / columns, column = i % columns;
            if (grid[row][column] == '*') {
                startRow = row;
                startColumn = column;
                break;
            }
        }
        visited[startRow][startColumn] = true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{startRow, startColumn});
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int row = cell[0], column = cell[1];
                if (grid[row][column] == '#')
                    return steps;
                for (int[] direction : directions) {
                    int newRow = row + direction[0], newColumn = column + direction[1];
                    if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && grid[newRow][newColumn] != 'X' && !visited[newRow][newColumn]) {
                        visited[newRow][newColumn] = true;
                        queue.offer(new int[]{newRow, newColumn});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

############

class Solution {
    private int[] dirs = {-1, 0, 1, 0, -1};

    public int getFood(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0, x = 1; i < m && x == 1; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '*') {
                    q.offer(new int[] {i, j});
                    x = 0;
                    break;
                }
            }
        }
        int ans = 0;
        while (!q.isEmpty()) {
            ++ans;
            for (int t = q.size(); t > 0; --t) {
                var p = q.poll();
                for (int k = 0; k < 4; ++k) {
                    int x = p[0] + dirs[k];
                    int y = p[1] + dirs[k + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (grid[x][y] == '#') {
                            return ans;
                        }
                        if (grid[x][y] == 'O') {
                            grid[x][y] = 'X';
                            q.offer(new int[] {x, y});
                        }
                    }
                }
            }
        }
        return -1;
    }
}

// OJ: https://leetcode.com/problems/shortest-path-to-get-food/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int getFood(vector<vector<char>>& G) {
        int M = G.size(), N = G[0].size(), sx = -1, sy = -1, step = 0, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        for (int i = 0; i < M && sx == -1; ++i) {
            for (int j = 0; j < N && sx == -1; ++j) {
                if (G[i][j] == '*') sx = i, sy = j;
            }
        }
        queue<pair<int, int>> q;
        q.emplace(sx, sy);
        G[sx][sy] = 'X';
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [x, y] = q.front();
                q.pop();
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || a >= M || b < 0 || b >= N || G[a][b] == 'X') continue;
                    if (G[a][b] == '#') return step + 1;
                    G[a][b] = 'X';
                    q.emplace(a, b);
                }
            }
            ++step;
        }
        return -1;
    }
};

class Solution:
    def getFood(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        i, j = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '*')
        q = deque([(i, j)])
        dirs = (-1, 0, 1, 0, -1)
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n:
                        if grid[x][y] == '#':
                            return ans
                        if grid[x][y] == 'O':
                            grid[x][y] = 'X'
                            q.append((x, y))
        return -1

func getFood(grid [][]byte) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := []int{-1, 0, 1, 0, -1}
	type pair struct{ i, j int }
	q := []pair{}
	for i, x := 0, 1; i < m && x == 1; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '*' {
				q = append(q, pair{i, j})
				x = 0
				break
			}
		}
	}
	for len(q) > 0 {
		ans++
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			for k := 0; k < 4; k++ {
				x, y := p.i+dirs[k], p.j+dirs[k+1]
				if x >= 0 && x < m && y >= 0 && y < n {
					if grid[x][y] == '#' {
						return ans
					}
					if grid[x][y] == 'O' {
						grid[x][y] = 'X'
						q = append(q, pair{x, y})
					}
				}
			}
		}
	}
	return -1
}

/**
 * @param {character[][]} grid
 * @return {number}
 */
var getFood = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [-1, 0, 1, 0, -1];
    const q = [];
    for (let i = 0, x = 1; i < m && x == 1; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] == '*') {
                q.push([i, j]);
                x = 0;
                break;
            }
        }
    }
    let ans = 0;
    while (q.length) {
        ++ans;
        for (let t = q.length; t > 0; --t) {
            const [i, j] = q.shift();
            for (let k = 0; k < 4; ++k) {
                const x = i + dirs[k];
                const y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n) {
                    if (grid[x][y] == '#') {
                        return ans;
                    }
                    if (grid[x][y] == 'O') {
                        grid[x][y] = 'X';
                        q.push([x, y]);
                    }
                }
            }
        }
    }
    return -1;
};

1730 - Shortest Path to Get Food

1730. Shortest Path to Get Food

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1730. Shortest Path to Get Food

Level

Description

Solution

All Problems

All Solutions