首页 > 专题系列 > Java解POJ > POJ 1321 棋盘问题 [解题报告] Java
2013
11-09

POJ 1321 棋盘问题 [解题报告] Java

棋盘问题

问题描述 :

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

输入:

输入含有多组测试数据。

每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n

当为-1 -1时表示输入结束。

随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

输出:

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

样例输入:

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));因为第二种解法如果数组有重复元素 就不正确