网站客户续费,传统网站和手机网站的区别,网站建设如何上传文件,房地产公司排行榜51. N 皇后#xff08;困难#xff09;
题目描述#xff1a; n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击#xff0c;即令其中任意两个皇后都不同列、同行和在一条斜线上。
给你一个整数 n #xff0c;返回所有不…51. N 皇后困难
题目描述 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击即令其中任意两个皇后都不同列、同行和在一条斜线上。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 考察重点需要找出所有情况应立刻想到DFS同时为了方便查找使用二维数组代替链表进行遍历。使用isLegal()函数判断斜边列是否存在QueenDFS按行进行递归每次在当前行寻找合法的列插入Queen并进入下一行。最终当递归到最后一行1时说明当前分布满足条件加入结果链表list。
ListListString list;
public boolean isLegal(char map[][], int x, int y){for(int i 0;i map.length;i ){if(map[i][y] ! .)return false;}for(int i 1;i map.length;i ){if(xi map.length yi map.length map[x i][y i] ! .)return false;if(x-i 0 y-i 0 map[x - i][y - i] ! .)return false;if(xi map.length y-i 0 map[x i][y - i] ! .)return false;if(x-i 0 yi map.length map[x - i][y i] ! .)return false;}return true;
}
public int dfs(char[][] map, int x){if(!(x map.length)){ListString single new ArrayList();for(int i 0;i map.length;i )single.add(String.valueOf(map[i]));list.add(single);return 0;}for(int y 0;y map.length;y ){if(isLegal(map, x, y)) {map[x][y] Q;dfs(map, x 1);map[x][y] .;}}return 0;
}
public ListListString solveNQueens(int n) {list new ArrayList();char[][] map new char[n][n];for(int i 0;i n;i )for(int j 0;j n;j )map[i][j] .;dfs(map, 0);return list;
}
