Lintcode33N-Queenssolution题解-创新互联
【题目描述】
成都创新互联公司专注于丽水网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供丽水营销型网站建设,丽水网站制作、丽水网页设计、丽水网站官网定制、微信平台小程序开发服务,打造丽水网络公司原创品牌,更为您提供丽水网站排名全网营销落地服务。The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互***。给定一个整数n,返回所有不同的n皇后问题的解决方案。每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。
【题目链接】
http://www.lintcode.com/en/problem/n-queens/
【题目解析】
经典的DFS递归回溯解法,大体思路就是对每一行,按每一列挨个去试,试到了就保存结果没试到就回溯。
难点大概就是用1个一维数组存皇后所在的坐标值。对于一个棋盘来说,每个点都有横纵坐标,用横纵坐标可以表示一个点。
而这道题巧就巧在,每一行只能有一个皇后,也就是说,对于一行只能有一个纵坐标值,所以用1维数组能提前帮助解决皇后不能在同一行的问题。
那么用一维数组表示的话,方法是:一维数组的下标表示横坐标(哪一行),而数组的值表示纵坐标(哪一列)。
这样一来,皇后所在的坐标值就能用一维数组表示了。而正是这个一维数组,在回溯找结果的时候不需要进行remove重置操作了,因为回溯的话正好就回到上一行了,就可以再重新找下一个合法列坐标了。
因为是按照每一行去搜索的,当行坐标值等于行数时,说明棋盘上所有行都放好皇后了,这时就把有皇后的位置标为Q,没有的地方标为0。
按照上面讲的那个一维数组,我们就可以遍历整个棋盘,当坐标为(row,columnVal[row])的时候,就说明这是皇后的位置,标Q就行了。
【参考答案】
http://www.jiuzhang.com/solutions/n-queens/
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:Lintcode33N-Queenssolution题解-创新互联
URL标题:http://myzitong.com/article/dsccii.html