p51

发表于 | 分类于 |

LeetCode 51 N-Queens 题解

1.题目：

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

题意：

N-Queens问题，Q表示皇后，.表示地，同一行列对角线上不能有其他皇后。

2.解题思路:

采用dfs,先博客的时候突然感觉是bfs来着，TUT，反正就是这样搜索下去啦。
解释下几个点，是否在同一条对角线是时用斜率计算的，45度的两条边相等。
每次添加一组答案都创建一个新对象不直接使用way进行赋值，原因是。。你用way试试看嘛，
都会变成way最后的值，也就是都是点点。你mark下的其实都是way这个对象TUT，它出门就变了TUT。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 

public class Solution {
    public  List<List<String>> solveNQueens(int n) {
		List<List<String>> ansArrayList = new ArrayList<List<String>>();

		if (n == 0)
			return null;
		List<String> ways = new ArrayList<String>();
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			s.append('.');
		}
		for (int i = 0; i < n; i++) {
			ways.add(s.toString());
		}

		dfs(n, ansArrayList, ways, 0);
		return ansArrayList;
	}

	public  void dfs(int n, List<List<String>> ansArrayList,
			List<String> ways,int row) {
		//if (row>0) System.out.println(ways.get(row-1));
		
		if (row==n)
		{
			List<String> aList=new ArrayList<String>() ;
			for (int i=0;i<ways.size();i++)
			{
				//System.out.println(ways.get(i));
				aList.add(ways.get(i));
			}//创建新对象赋值
			
			ansArrayList.add(aList);
			
			return;
		}
		
		for (int j=0;j<n;j++)
		{
			if (check(n,ways,row,j))
			{
				StringBuilder s = new StringBuilder(ways.get(row));
				s.setCharAt(j, 'Q');
				ways.set(row, s.toString());
				dfs(n, ansArrayList, ways, row+1);
				s.setCharAt(j, '.');
				ways.set(row, s.toString());
			}
		}
	}

	public  boolean check(int n,List<String> ways, int r, int l) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < n; j++) {
				if (ways.get(i).charAt(j) == 'Q'
						&& (j == l || Math.abs(r - i) == Math.abs(l - j))) {
					return false;
				}
			}
		}
		return true;

	}
}

4.一些总结：