1. 首页

LeetCode 051. N皇后

题目描述:

难度:Hard

相关话题:回溯算法

n 皇后问题研究的是如何将 n 个皇后放置在 n ×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

LeetCode 051. N皇后

上图为 8 皇后问题的一种解法。

给定一个整数 n ,返回所有不同的n 皇后问题的解决方案。

每一种解法包含一个明确的n 皇后问题的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路:

经典的回溯问题,主要思想就是不断尝试每一行每一个位置能否放置Q

定义3个hash,用来保存已经放置的Q能攻击到的范围,分别是coldia1dia2(竖线和2对角线)

并且定义一个board来记录每个Q放置的位置,因为最终输出需要输出整个棋盘位置。

由于每一行最多只可能存在一个Q,那么如果第i行放置了,那么就继续第i+1行,检查是否有位置能放置。

检查的过程有一个高效的方法,col很简单,关键在两条斜线,可以思考这两条斜线的延长线最终到达第一行的位置。

左下到右上斜线[i,j]延长线最终能到达第一行的位置就是[0,j+i],因此只需要保存j+i

左上到右下的斜线[i,j]延长线最终能到达第一行的位置就是[0,j-i],因此只需要保存j-i

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  let dia1=Array(2*n).fill(false),
      dia2=Array(2*n).fill(false),
      col=Array(n).fill(false)
  let board=Array(n).fill().map(()=>Array(n).fill('.'))
  let res=[]
  backtrack(board,0,0)
  return res
  function backtrack(board,setCount,rowId){
    if(setCount===n){
      let ans=[]
      for(let i=0;i<n;i++){
        ans.push(board[i].join(''))
      }
      res.push(ans)
    }
    for(let j=0;j<n;j++){
      let lt2rd=j-rowId+n,rt2ld=j+rowId
      // 检查竖线,两斜线是否冲突
      if(col[j] || dia1[lt2rd] || dia2[rt2ld])continue
      col[j]=true
      dia1[lt2rd]=true
      dia2[rt2ld]=true
      board[rowId][j]="Q"
      backtrack(board,setCount+1,rowId+1)
      board[rowId][j]="."
      dia2[rt2ld]=false
      dia1[lt2rd]=false
      col[j]=false
    }
  }
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 051. N皇后

链接:https://www.javascriptc.com/4411.html

« 带你0.1分钟将vscode撸成小霸王
LeetCode 050. Pow(x, n)»
Flutter 中文教程资源

相关推荐

QR code