2013
11-09

# 棋盘问题

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1


2
1


import java.util.Scanner;

public class Main {

private static int n;
private static int k;
private static int ans;
private static int[] column;
private static String[] chessboard;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {
n = sc.nextInt();
k = sc.nextInt();
if (n == -1 && k == -1)
break;
sc.nextLine();
chessboard = new String[n];
column = new int[n];
for (int i = 0; i < n; i++) {
chessboard[i] = sc.nextLine();
}
ans = 0;
dfs(0, 0);// 从第一行开始
System.out.println(ans);
}
}

private static void dfs(int pos, int i) {

if (pos == k) {
ans++;
return;
}
if (i >= n)
return;
for (int j = 0; j < n; j++) {
char ch = chessboard[i].charAt(j);
if (ch == '#' && column[j] == 0) {
column[j] = 1;
pos++;
dfs(pos, i + 1);
column[j] = 0;
pos--;
}
}
dfs(pos, i + 1);
}

}

1. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确