LeetCode 1219. Path with Maximum Gold

Problem Statement

BFS.

use std::collections::VecDeque;
use std::cmp;

impl Solution {
    pub fn get_maximum_gold(grid: Vec<Vec<i32>>) -> i32 {
        let (m, n, mut ans, mut id) = (grid.len(), grid[0].len(), 0, 0);
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([0, 0, 1, -1], [1, -1, 0, 0]);
        let mut visited = vec![vec![0; n]; m];
        let mut q = VecDeque::new();

        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 0 {
                    continue;
                }
                id += 1;
                visited[i][j] = 1 << id;
                q.push_back((i, j, grid[i][j], visited[i][j]));
            }
        }

        while !q.is_empty() {
            let cur = q.pop_front().unwrap();
            let (x, y, sum, state) = (cur.0 as i32, cur.1 as i32, cur.2, cur.3);
            ans = cmp::max(ans, sum);
            for i in 0..4 {
                let (xx, yy) = (x + dx[i], y + dy[i]);
                if xx < 0 || xx == m as i32 || yy < 0 || yy == n as i32 ||
                    grid[xx as usize][yy as usize] == 0 || (state & visited[xx as usize][yy as usize] != 0) {
                    continue;
                }
                let (nx, ny) = (xx as usize, yy as usize);
                q.push_back((nx, ny, sum + grid[nx][ny], state | visited[nx][ny]));
            }
        }

        return ans;
    }
}