Untitled
unknown
plain_text
2 years ago
3.1 kB
6
Indexable
import java.io.FileInputStream; import java.util.Scanner; public class QuanHau { static int a[][]; static int visit[][]; static int N; static int ans; static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 }; static int debug = 1; // public static boolean checkAnToan(int hang, int cot) { // if (visit[hang][cot] != 0) // return false; // return true; // } public static boolean checkFullRow(int hang) { for (int i = 0; i < N; i++) { if (visit[hang][i] == 0) return true; // chua full } return false; } public static void visitRow(int hang, int cot) { if(debug==1) System.out.println("visit:"); visit[hang][cot]++; for (int i = 0; i < 8; i++) { for (int t = 1;; t++) { int nextX = hang + dx[i] * t; int nextY = cot + dy[i] * t; if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) { visit[nextX][nextY]++; } else break; } } if (debug == 1) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { System.out.print(visit[i][j] + " "); } System.out.println(); } System.out.println(); } // for(int i=0; i<N; i++) // { // visit[hang][i]++; // if(i!=hang) // visit[i][cot]++; // } // // int xRow = hang+1; // int xCol = cot+1; // while(xRow<N&&xCol<N){ // visit[xRow][xCol]++; // } } public static void unVisitRow(int hang, int cot) { if(debug==1) System.out.println("unvisit:"); visit[hang][cot]--; for (int i = 0; i < 8; i++) { for (int t = 1;; t++) { int nextX = hang + dx[i] * t; int nextY = cot + dy[i] * t; if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) visit[nextX][nextY]--; else break; } } if (debug == 1) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { System.out.print(visit[i][j] + " "); } System.out.println(); } System.out.println(); } } // public static void print() { // for (int i = 0; i < 4; i++) { // for (int j = 0; j < 4; j++) { // System.out.print(a[i][j] + " "); // } // System.out.println(); // } // } public static void backTrack(int hang, int numQueen) { if (numQueen == N) { //xet truoc dong 104 ans++; return; } if (hang == N) return; if (!checkFullRow(hang)) return; for (int i = 0; i < N; i++) { // tung vi tri trong hang if (visit[hang][i]==0) { if (debug == 1) System.out.println("row:" + hang + " cot" + i); visitRow(hang, i); backTrack(hang + 1, numQueen + 1); unVisitRow(hang, i); } } } public static void main(String args[]) throws Exception { System.setIn(new FileInputStream("QuanHau.txt")); Scanner sc = new Scanner(System.in); int T; T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { N = sc.nextInt(); a = new int[N][N]; ans = 0; visit = new int[N][N]; backTrack(0, 0); System.out.println("Case #" + test_case + ": " + ans); } } }
Editor is loading...