Problem 161 (C++で)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <map>
using namespace std;
int h=12,w=9;
int area[][3]={{0,w,w+1},{0,w,w-1},{0,w+1,1},{0,w,1},{0,w,2*w},{0,1,2}};
bool inBoard(int x,int t){
  switch(t){
  case 1: return x/w<h-1 && x%w>0;
  case 4: return x/w<h-2;
  case 5: return x%w<w-2;
  default: return x/w<h-1 && x%w<w-1;
  }
}
bool canPut(bool board[],int x,int t){
  if(!inBoard(x,t))return false;
  for(int i=0;i<3;i++)if(board[x+area[t][i]])return false;
  return true;
}
long shape(bool board[]){
  long long s=0;
  for(int i=0,j,t,p;i<w;i++,s=2*h*s+t+p)
    for(p=0,t=0,j=0;j<h;j++)if(board[w*j+i]){
	p=t;
	t=j+1;
      }
  return s;
}
long long solve(map<long,long long> &memo,bool board[],int x){
  long s = shape(board);
  if(memo.find(s)!=memo.end()) return memo[s];
  if(x==h*w) return 1;
  if(board[x]) return solve(memo,board,x+1);
  long long count=0;
  for(int t=0;t<6;t++)
    if(canPut(board,x,t)){
      for(int i=0;i<3;i++)board[x+area[t][i]]=true;
      count+=solve(memo,board,x+1);
      for(int i=0;i<3;i++)board[x+area[t][i]]=false;
    }
  if(count>1) memo[s]=count;
  return count;
}
int main(){
  bool board[h*w];
  map<long,long long> memo;
  for(int i=0;i<h*w;i++)board[i]=false;
  cout << solve(memo,board,0) << "\n";
}

1

int[] arr;

1

void func(int[] arr){

1

int arr[]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#define H 12
#define W 9
#define S 1953125
using namespace std;
int area[][3]={{0,W,W+1},{0,W,W-1},{0,W+1,1},{0,W,1},{0,W,2*W},{0,1,2}};
bool inBoard(int x,int t){
  switch(t){
  case 1: return x/W<H-1 && x%W>0;
  case 4: return x/W<H-2;
  case 5: return x%W<W-2;
  default: return x/W<H-1 && x%W<W-1;
  }
}
bool canPut(bool board[],int x,int t){
  if(!inBoard(x,t))return false;
  for(int i=0;i<3;i++)if(board[x+area[t][i]])return false;
  return true;
}
int shape(bool board[],int z){
  int s=0;
  for(int i=0,t=0;i<W;i++,s=5*s+t,t=0)
    for(int j=0;j<3&&(z+j)*W+i<H*W;j++)
      if(board[(z+j)*W+i])t+=j==1? 2: 1;
  return s;
}
long long solve(long long memo[][S],bool board[],int x){
  if(x==H*W) return 1;
  if(board[x]) return solve(memo,board,x+1);
  int z=x/W,s=shape(board,z);
  if(memo[z][s]>0) return memo[z][s];
  long long count=0;
  for(int t=0;t<6;t++)
    if(canPut(board,x,t)){
      for(int i=0;i<3;i++)board[x+area[t][i]]=true;
      count+=solve(memo,board,x+1);
      for(int i=0;i<3;i++)board[x+area[t][i]]=false;
    }
  memo[z][s]=count;
  return count;
}
int main(){
  bool board[H*W];
  long long (*memo)[S]=new long long[H][S];
  for(int i=0;i<H*W;i++)board[i]=false;
  for(int i=0;i<H;i++)for(int j=0;j<S;j++)memo[i][j]=-1;
  cout << solve(memo,board,0) << "\n";
  delete [] memo;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

import java.util.*;
public class P161_1{
    static long[][] memo;
    static boolean[] board;
    static int h=12,w=9;
    static long solve(int x){
	if(x==h*w)return 1;//finish 
	if(board[x])return solve(x+1);//filled
	int z = x/w,s=shape(z);
	if(memo[z][s]>0)return memo[z][s];
	long count=0;
	for(Triomino t:EnumSet.range(Triomino.NorthEast,Triomino.Horizon))//next step
	    if(canPut(x,t)){
		for(int y:t.area(w))board[x+y]=true;//put Triomino
		count+=solve(x+1);
		for(int y:t.area(w))board[x+y]=false;//remove Triomino
	    }
	memo[z][s]=count;
	return count;
    }
    static boolean canPut(int x,Triomino t){
	if(!t.canPut(h,w,x))return false;
	for(int y:t.area(w))if(board[x+y])return false;
	return true;
    }
    static int shape(int z){
	int s=0;
	for(int i=0,t=0;i<w;i++,s=5*s+t,t=0)
	    for(int j=0;j<3&&(z+j)*w+i<h*w;j++)
		if(board[(z+j)*w+i])t+=j==1? 2: 1;
	return s;
    }
    public static void main(String[] args){
	board=new boolean[h*w];
	memo = new long[h][(int)Math.pow(5,w)];
	for(int i=0;i<h;i++)Arrays.fill(memo[i],-1);
	System.out.println("result:"+solve(0));
    }
}
enum Triomino{
    NorthEast,NorthWest,SouthWest,SouthEast,Vertical,Horizon;
    public int[] area(int w){
	switch(this){
	case NorthEast: return new int[] {0,w,w+1};
	case NorthWest: return new int[] {0,w,w-1};
	case SouthWest: return new int[] {0,w+1,1};
	case SouthEast: return new int[] {0,w,1};
	case Vertical: return new int[] {0,w,2*w};
	case Horizon: return new int[] {0,1,2};
	default: return null;
	}
    }
    public boolean canPut(int h,int w,int x){
	switch(this){
	case NorthWest: return x/w<h-1 && x%w>0;
	case Vertical: return x/w<h-2;
	case Horizon: return x%w<w-2;
	default: return x/w<h-1 && x%w<w-1;
	}
    }
}