Untitled

 avatar
unknown
plain_text
9 months ago
1.2 kB
6
Indexable
// Painting
package backtrack;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Painting {
	public static int n, count;
	public static int[][] map;
	public static int[][] color;
	
	public static boolean isDatDuocMau(int a, int c) {
		for (int i = 0; i < n; i++) {
			if (map[a][i] == 1 && color[i][c] == 1) {
				return false;
			}
		}
		return true;
	}
	
	public static void deQuy(int i) {
		if (i == n) {
			count++;
			return;
		}
		for (int c = 0; c < 4; c++) {
			if(isDatDuocMau(i, c)) {
				color[i][c] = 1;
				if (i < n) {
					deQuy(i + 1);
				}
				color[i][c] = 0;
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException{
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("C:/Users/srv_training/workspace/testabc/src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int t1 = 1; t1 <= t; t1++) {
			count = 0;
			map = new int[n][n];
			color = new int[n][4];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			deQuy(0);
			System.out.println("Case #" + t1);
			System.out.println(count);
		}
		sc.close();
	}
}
Editor is loading...
Leave a Comment