Tiling Spoj 2530 and related

Time to Tile some Dominoes

http://www.spoj.com/problems/M3TILE/

http://www.spoj.com/problems/GNY07H/ (M4TILE)

http://www.spoj.com/problems/M5TILE/ (M5TILE)

(M3TILE) : https://gist.github.com/swapcoder/6738962
(M4TILE) : https://gist.github.com/swapcoder/6738982

i will explain the (M4TILE) and posted (M4TILE) and (M3TILE) codes , last one i will post later

problem can be broken up into 3 subproblems

Sub problems
Check code for related recurrence relations

UVA 11553 :: GRID

Going through all permutation as test input is small. this is JAVA solution. its time limit exceeds , you will get accept in C++ use next_permutation function. this code is nice to see how actual permutation would be designed.

	import java.util.Scanner;
	/*
	* To change this template, choose Tools | Templates
	* and open the template in the editor.
	*/
	/**
	*
	* @author piyush
	*/
	public class Main {
	static int grid[][]=new int[10][10];
	static int n;
	static int min=10000000;
	public static void main(String args[])
	{
	int a[]=new int[20];
	Scanner sc = new Scanner(System.in);
	int T=sc.nextInt();
	while(0!=T--)
	{
	n=sc.nextInt();
	for(int i=0;i<n;i++)
	{
	for(int j=0;j<n;j++)
	{
	grid[i][j]=sc.nextInt();
	}
	}
	for(int i=0;i<n;i++)
	{
	a[i]=i;
	}
	min=10000000;
	permu(0,a,n);
	System.out.println(min);
	}
	}
	public static void permu(int a,int arr[],int n)
	{
	if(a==n-1)
	{
	int sum=0;
	for(int i=0;i<n;i++)
	{
	sum=sum+grid[i][arr[i]];
	System.out.print(arr[i]+" ");
	}
	System.out.println();
	if(sum<min)min=sum;
	return ;
	}
	else
	{
	for(int j=a;j<n;j++)
	{
	int temp=arr[j]; arr[j]=arr[a]; arr[a]=temp;
	permu(a+1,arr,n);
	temp=arr[j]; arr[j]=arr[a]; arr[a]=temp;
	}
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub