AnyJohn 的网络博客

18. Place N Cameras Without Conflict on Blocked Grid

Properties1
tags算法, 回溯, n皇后, hackerrank

5分钟阅读

18. Place N Cameras Without Conflict on Blocked Grid

Origin: Place N Cameras Without Conflict on Blocked Grid

Given an NxN grid where 0 is empty and 1 is blocked, return true if N cameras can be placed on empty cells such that no two share the same row, column, or diagonal.

本质上是 N 皇后问题，grid 里的 1 表示该格被阻挡（不能放相机）。

Example 1

Input: N = 4, grid = [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]

Output: True

Explanation: One valid placement: Row 0→col 1, Row 1→col 3, Row 2→col 0, Row 3→col 2. No two share row, column, or diagonal.

Example 2

Input: N = 4, grid = [[0,1,0,0], [0,0,0,1], [1,0,0,0], [0,0,1,0]]

Output: True

Explanation: Some cells are blocked (marked 1). Placement: Row 0→col 2, Row 1→col 0, Row 2→col 3, Row 3→col 1. All on empty cells, no conflicts.

Input Format

  • N（整数，网格大小）
  • grid_rows（整数，行数 = N）
  • grid_columns（整数，列数 = N）
  • 接下来 grid_rows 行，每行 grid_columns 个整数（0 或 1）

Constraints

  • 1 <= N <= 15
  • grid.length == N
  • grid[i].length == N
  • grid[i][j] ∈ {0, 1}

Output Format

Return a single boolean value (true or false) indicating whether a valid arrangement of N cameras exists.

Sample Input 0

1
1
1
0

Sample Output 0

1

Sample Input 1

2
2
2
0 1
1 0

Sample Output 1

0

函数契约

// 输入：N（网格大小），grid（NxN 的 0/1 矩阵，1 表示阻挡）
// 输出：true 或 false（能否放 N 个相机，互不攻击）
// 边界：N=1 且 grid[0][0]=0 → true；N=1 且 grid[0][0]=1 → false

边界表

场景返回什么
N=1, grid[0][0]=0true
N=1, grid[0][0]=1false
全部阻挡false
无解false
有解true

Resolution

我的解法

function canPlaceSecurityCameras(N: number, grid: number[][]): boolean {
    let res = false
 
    const placeCamera = (row: number, cols: number[], diag1s: number[], diag2s: number[]) => {
        if (res) return  // 已找到解，提前退出
        for (let i = 0; i < N; i++) {
            const isPlaceable = grid[row][i] === 0 && !cols.includes(i) && !diag1s.includes(row - i) && !diag2s.includes(row + i)
            if (row === N - 1 && isPlaceable) {
                res = true
                return
            }
            if (isPlaceable) {
                placeCamera(row + 1, [...cols, i], [...diag1s, row - i], [...diag2s, row + i])
            }
        }
    }
    placeCamera(0, [], [], [])
    return res
}

解题思路

逐行放置，每行选一个列。用三个数组记录冲突：

  • cols：已占用的列
  • diag1s：已占用的主对角线（row - col 相同）
  • diag2s：已占用的副对角线（row + col 相同）

对每个格子检查四个条件：grid 为空（值为 0）、列不冲突、主对角线不冲突、副对角线不冲突。全部满足才能放。放到最后一行说明 N 个相机全部放完，返回 true。

找到解后用 if (res) return 提前退出，N=15 时能省大量递归。

对角线判断原理

同一条主对角线上的格子，row 和 col 的差值相同。比如 (0,0)、(1,1)、(2,2) 差值都是 0；(0,2)、(1,3) 差值都是 -2。

同一条副对角线上的格子，row 和 col 的和相同。比如 (0,2)、(1,1)、(2,0) 和都是 2。

所以用 row - col 标识主对角线，row + col 标识副对角线，放相机时把对应值加入冲突列表，后续格子检查是否在列表中即可。

踩坑经历

第一版递归传参用了函数参数 col 而不是循环变量 i，导致冲突列表存的是错误的值。修正后把 col 参数去掉，直接用循环变量 i 传递。

复杂度

  • 时间：O(N!)，每行可选列数递减（N × (N-1) × (N-2) × … × 1）
  • 空间：O(N)，递归栈深度 N，三个冲突列表各最多 N 个元素

测试用例

输入输出场景
N=1, grid=0true单格可放
N=1, grid=1false单格阻挡
N=2, grid=[[0,1],[1,0]]false2x2 无解
N=4, grid=全0true4x4 全空
N=4, grid=有阻挡true4x4 有阻挡
N=3, grid=全1false全阻挡

全部通过。

参考来源

关系图谱

近期发布