Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.2 kB
1
Indexable
Never
#include <stdio.h>

int visited[7][8];
int matrix[7][8];
int F[7][7];
int result = 0;
int dx[2] = {0, 1};
int dy[2] = {1, 0};
void load_domino_in_matrix(int x, int y)
{
	if(x==7)
	{
		result++;
		return;
	}
	if(visited[x][y]==0)
	{
		int one, two;
		one = matrix[x][y];
		for(int i=0; i<2; i++)
		{
			int tempx = x + dx[i];
			int tempy = y + dy[i];
			if(tempx>=0&&tempx<7&&tempy>=0&&tempy<8&&visited[tempx][tempy]==0)
			{
				two = matrix[tempx][tempy];
				if(one<=two && F[one][two])
				{
					F[one][two] = 0;
					visited[x][y] = visited[tempx][tempy] = 1;
					if(y<7)load_domino_in_matrix(x, y+1);
					else load_domino_in_matrix(x+1, 0);
					visited[x][y] = visited[tempx][tempy] = 0;
					F[one][two] = 1;
				}
				else if(F[two][one])
				{
					F[two][one] = 0;
					visited[x][y] = visited[tempx][tempy] = 1;
					if(y<7)load_domino_in_matrix(x, y+1);
					else load_domino_in_matrix(x+1, 0);
					visited[x][y] = visited[tempx][tempy] = 0;
					F[two][one] = 1;
				}
			}
		}
	}
	else
	{
		if(y<7)load_domino_in_matrix(x, y+1);
		else load_domino_in_matrix(x+1, 0);
	}
}

int main()
{
	int number_test, i, j, test;
	for(int i=0; i<=6; i++)
		for(int j=i; j<=6; j++)
			F[i][j] = 1;
	scanf("%d", &number_test);
	for(test=0; test<number_test; test++)
	{
		for(i=0; i<7; i++)
			for(j=0; j<8; j++)
				scanf("%d", &matrix[i][j]);
		result = 0;
		load_domino_in_matrix(0, 0);
		printf("%d\n", result);
	}

}



package Domino;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int board[][] = new int[7][8];
	static int visited[][] = new int[7][8];
	static int domino[][] = new int[7][8];
	static int count;
	static int dx[] = { 1, 0 };
	static int dy[] = { 0, 1 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for (int tc = 1; tc <= test; tc++) {
			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 8; j++) {
					domino[i][j] = visited[i][j] = 0;
					board[i][j] = sc.nextInt();
				}
			}
			count = 0;
			backtrack(0);
			System.out.println("#" + tc+" "+count);
		}
	}

	public static boolean check(int x, int y) {
		if (x >= 0 && x < 7 && y >= 0 && y < 8)
			return true;
		else
			return false;
	}

	public static void backtrack(int x) {
		// TODO Auto-generated method stub
		if (x == 56) {
			count++;
			return;
		}
		int a = x / 8;
		int b = x % 8;
		if (visited[a][b] == 0) {
			for (int z = 0; z < 2; z++) {
				int aa = a + dx[z];
				int bb = b + dy[z];
				if(check(aa,bb) && visited[aa][bb] == 0 && domino[board[a][b]][board[aa][bb]]==0){
					visited[aa][bb] = 1;
					visited[a][b] = 1;
					domino[board[a][b]][board[aa][bb]] = 1;
					domino[board[aa][bb]][board[a][b]] = 1;
					backtrack(x+1);
					visited[aa][bb] = 0;
					visited[a][b] = 0;
					domino[board[a][b]][board[aa][bb]] = 0;
					domino[board[aa][bb]][board[a][b]] = 0;
				}
			}
			return;
		}
		else{
			backtrack(x+1);
		}
	}
}