Leetcode 864疑问

Question

/**
 * @param {string[]} grid
 * @return {number}
 */
var shortestPathAllKeys = function(grid) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let visited=[]; // 是否访问过
    const R = grid.length, C = grid[0].length;
    let startR = -1, startC = -1;
    let keyTotal = 0; // 总共有多少钥匙, lockKey == keyTotal,说明都找到钥匙了
    let lockKey = 0; // 找到的钥匙数量
    let key2lock={}; // 钥匙->锁
    let lock2key={}; // 锁->钥匙
    

    // 定义地图,并找到起点, 同时初始化visited数组
    for(let r = 0; r < R; r ++ ){
        visited[r]=[];
        for( let c = 0; c < C; c ++ ){
            visited[r][c] = false;
            if( grid[r][c] == '@' ){
                startR = r; // 起点
                startC = c;
            }else if( islower( grid[r][c] ) ){
                keyTotal ++;
            }
        } // for c
    } // for r

    let queue = [[startR, startC, 0]]; // bfs 队列, [行, 列, 步数]
    while( queue.length > 0 ){

        let [nowR, nowC, nowStep] = queue.shift(); // 出一个队列头

        // 看下手上是否有了所有钥匙
        if( lockKey == keyTotal ){
            return nowStep;
        }

        for( let d = 0; d < dirs.length; d ++ ){
            let newR = nowR + dirs[d][0], newC = nowC + dirs[d][1];
            if( !inArea(R, C, newR, newC) ){  // 如果超过边界
                continue;
            }
            if( grid[newR][newC] == '#' ){ // 如果是 墙壁
                continue;
            }

            // 是否访问过
            if( visited[newR][newC] ){
                continue;
            }

            // 是否是钥匙
            if( islower( grid[newR][newC] ) ){
                visited[newR][newC] = true;
                lockKey ++; // 找到一把钥匙
                key2lock[grid[newR][newC]] = grid[newR][newC].toUpperCase(); // 一把钥匙对应一把锁
                lock2key[grid[newR][newC].toUpperCase()] = grid[newR][newC]; // 一把锁对一把钥匙

                queue.push( [newR, newC, nowStep + 1] ); // 入队
            }else if( isupper( grid[newR][newC]  ) ){ // 是否是锁
                // 看有没有对应这把锁的钥匙
                if( lock2key[grid[newR][newC]] ){
                    // 说明能通过这把锁
                    visited[newR][newC] = true;

                    queue.push( [newR, newC, nowStep + 1] ); // 入队
                }
            }else{
                // 说明是空房间 '.'
                queue.push( [newR, newC, nowStep + 1] ); // 入队
                visited[newR][newC] = true;
            }

        } // for d

    } // end while queue.length

    return -1;
};

function inArea( R, C, r, c ){
    return r >= 0 && r < R && c >= 0 && c < C;
}

function islower(ch){
    let reg = /^[a-z]$/;
    return reg.test(ch);
}

function isupper(ch){
    let reg = /^[A-Z]$/;
    return reg.test(ch);
}

最新的代码，visited包含钥匙信息

/**
 * @param {string[]} grid
 * @return {number}
 */
var shortestPathAllKeys = function(grid) {
    const dirs=[[0, -1], [0, 1], [-1, 0], [1, 0]];
    const R = grid.length, C = grid[0].length;
    let startR, startC;
    let keyCount = 0;

    for( let r = 0; r < R; r ++ ){
        for( let c = 0; c < C; c ++ ){
            if( grid[r][c] == '@' ){
                startR = r;
                startC = c;
            }else if( islower( grid[r][c] )  ){
                keyCount ++;
            }
        } // for c
    } // for r

    const KeyLen = 1 << keyCount;
    let visited = [];
    for( let r = 0; r < R; r ++ ){
        visited[r] = [];
        for( let c = 0; c < C; c ++ ){
            visited[r][c] = [];
            for( let h = 0; h < KeyLen; h ++ ){
                 // ************变动点 **********
                visited[r][c][h] = -1; // 这里不再是布尔值变量,设定成 到达 【r, c, h】这三个状态的步数
            } // for h
        } // for c
    } // for r


    // BFS
    let queue = [ [startR, startC, 0] ];
    visited[startR][startC][0] = 0;
    let step = 0;

    while( queue.length > 0 ){

        let [nowR, nowC, keyState] = queue.shift();

        if( keyState == KeyLen - 1 ){
            return visited[nowR][nowC][keyState];
        }

        for( let d = 0; d < 4; d ++ ){
            let newR = nowR + dirs[d][0], newC = nowC + dirs[d][1];
            if( !inArea( R, C, newR, newC ) ){
                continue;
            }

            if( grid[newR][newC] == '#' ){
                continue;
            }

            if( isupper(grid[newR][newC]) && ((1<<(grid[newR][newC].charCodeAt(0) - 'A'.charCodeAt(0))) & keyState) == 0 ){
                continue;
            }

            let newKeyState = keyState;

            if( islower(grid[newR][newC]) ){
                newKeyState = keyState | ( 1 << (grid[newR][newC].charCodeAt(0) - 'a'.charCodeAt(0)) );
                
            }
             // ************变动点 **********
            if( visited[newR][newC][newKeyState] != -1 ){ // 如果是-1，说明未访问
                    continue;
                }
                // ************变动点 **********
            visited[newR][newC][newKeyState] = visited[nowR][nowC][keyState] + 1; //这里【nowR,nowC, keyState】=>【newR, newC, newKeyState】
            queue.push( [ newR, newC, newKeyState ] ); // 把新的【newR, newC, newKeyState】压入队列中

        } // for d
        // step ++;
    } // end while queue.length
    return -1;
};

function inArea( R, C, r, c ){
    return r >= 0 && r < R && c >= 0 && c < C;
}

function islower( ch ){
    const reg = /^[a-z]$/;
    return reg.test(ch);
}

function isupper( ch ){
    const reg = /^[A-Z]$/;
    return reg.test(ch);
}

老师，上述我对visited三维数组作了语义上的更改，对visited这个查找表，【行，列，钥匙状态】作为key对应的值不再是布尔值真假，而是改为到达【行，列，钥匙状态】的步数了，即
【正在考查的行，正在考查的列，正在考查的钥匙状态】的value=【现在的行，现在的列，现在的钥匙状态】的value + 1, 这样改就是您说的step转成了和(x, y)一样的状态变量了。程序通过了AC

Answer 1

liuyubobobo 2022-11-13 01:26:55

这个算法看起来有问题。当你到达同一个点的时候，由于路径的不同，有可能手中的钥匙是不同的，你的算法是如何区分的？

• 提问者 甲骨文_0001 #1

  因为我想只要能取到所有钥匙就好了，然后代码中62行开始if( isupper( grid[newR][newC]  ) ){ // 是否是锁(此时遇到了一把锁)，我会检查目前手上的钥匙能不能打开这把锁，能打开，就能通过(此时锁就像一个空房间一样)。如果不能打开，就相当于一堵墙。然后老师你说的【当你到达同一个点的时候，由于路径的不同，有可能手中的钥匙是不同的】这个我想不影响问题的解决，因为我只要能取到所有钥匙，也就是 lockKey == keyTotal就好了。

• liuyubobobo 回复 提问者 甲骨文_0001 #2

  我现在不好说不检测具体的钥匙是否是正确的，但即便不检测具体的钥匙，只检测钥匙的数量，现在你的代码也肯定是不对的，因为你的 lockKey 是一个全局变量，但实际上 lockKey 应该是状态的一部分。
  
  一个简单的例子是：
  ```
  @aA
  b.B
  ```
  
  你的程序将返回 1，因为两把钥匙都在一步之内就拿到了。但是你必须先拿一把，再拿一把。不可能是 1。（正确答案是 3）

• 提问者 甲骨文_0001 回复 liuyubobobo #3

  嗯嗯，老师你的用例很好，对，在一次对相邻单元格检测的过程中，两把钥匙都取到了，此时lockKey=2,但是入队的时候是[0行，1列,  1], [1行，0列，1], 所以最后得到的总步数是1, 就是我要怎么改，一下想不到。。。。

点开查看后面7条评论