学步园

dfs深搜，不需要剪枝。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1321package poj1321;</p> <p>import java.util.Scanner;</p> <p>public class Main {</p> <p> private static int n;<br /> private static int k;<br /> private static int ans;<br /> private static int[] column;<br /> private static String[] chessboard;</p> <p> public static void main(String[] args) {</p> <p> Scanner sc = new Scanner(System.in);</p> <p> while (sc.hasNext()) {<br /> n = sc.nextInt();<br /> k = sc.nextInt();<br /> if (n == -1 && k == -1)<br /> break;<br /> sc.nextLine();<br /> chessboard = new String[n];<br /> column = new int[n];<br /> for (int i = 0; i < n; i++) {<br /> chessboard[i] = sc.nextLine();<br /> }<br /> ans = 0;<br /> dfs(0, 0);// 从第一行开始<br /> System.out.println(ans);<br /> }<br /> }</p> <p> private static void dfs(int pos, int i) {</p> <p> if (pos == k) {<br /> ans++;<br /> return;<br /> }<br /> if (i >= n)<br /> return;<br /> for (int j = 0; j < n; j++) {<br /> char ch = chessboard[i].charAt(j);<br /> if (ch == '#' && column[j] == 0) {<br /> column[j] = 1;<br /> pos++;<br /> dfs(pos, i + 1);<br /> column[j] = 0;<br /> pos--;<br /> }<br /> }<br /> dfs(pos, i + 1);<br /> }</p> <p>}<br />