N-Queens
n皇后的问题, 给一个数字n, 求返回一个地图, 地图上的每个皇后上下左右都没有别的皇后.直接dfs做..
|
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 |
public class Solution { public ArrayList<String[]> solveNQueens(int n) { ArrayList<String[]> res = new ArrayList<String[]>(); int[] loc = new int[n]; dfs(res, loc, 0, n); return res; } public void dfs(ArrayList<String[]> res, int[] loc, int cur, int n) { if(cur == n) { print(res, loc, n); return; } for(int i = 0; i < n; i++) { loc[cur] = i; if(isValid(loc, cur)) dfs(res, loc, cur+1, n); } } public boolean isValid(int[] loc, int cur) { for(int i = 0 ; i < cur; i++) { if(loc[i] == loc[cur] || Math.abs(loc[i]-loc[cur]) == (cur-i)) return false; } return true; } public void print(ArrayList<String[]> res, int[] loc, int n) { String[] ans = new String[n]; for(int i = 0 ; i < n; i++) { String row = new String(); for(int j = 0; j < n; j++) { if(j == loc[i]) row+="Q"; else row += "."; } ans[i] = row; } res.add(ans); } } |