明治ブラックチョコパズル
研究室にあったパズルを崩したら戻せなくなったので仕方なく全探索のプログラムを書いた.
- 出版社/メーカー: ハナヤマ
- 発売日: 2006/01/20
- メディア: おもちゃ&ホビー
- 購入: 3人 クリック: 21回
- この商品を含むブログ (5件) を見る
import static java.lang.Math.*; import static java.util.Arrays.*; import static java.util.Collections.*; import java.util.*; import java.io.*; public class Choco { private void run() { Scanner sc = new Scanner(System.in); int h = sc.nextInt(), w = sc.nextInt(); int cnum = sc.nextInt(); ArrayList<Parts> chocolates = new ArrayList<Parts>(); for(int i=0;i<cnum;++i){ int ch = sc.nextInt(), cw = sc.nextInt(); boolean[][] c = new boolean[ch][cw]; for(int j=0;j<ch;++j){ String s = sc.next(); for(int k=0;k<cw;++k)c[j][k]=(s.charAt(k)=='x'); } chocolates.add(new Parts(c)); } int table[][] = new int[h][w]; System.out.println(solve(chocolates,table,'a')); } boolean solve(ArrayList<Parts> ps, int[][] table, int num){ int h = table.length; int w = table[0].length; if(ps.size()==0){ show(table); return true; } int x=0,y=0; l:for(x=0;x<h;++x)for(y=0;y<w;++y)if(table[x][y]==0)break l; for(int i=0;i<ps.size();++i){ boolean[][][] pss = ps.get(i).getParts(); for(int j=0;j<4;++j){ boolean[][] p = pss[j]; int ph = p.length; int pw = p[0].length; int px=0,py=0; l:for(px=0;px<ph;++px)for(py=0;py<pw;++py)if(p[px][py])break l; if(x-px<0||y-py<0||x-px+ph>h||y-py+pw>w)continue; int[][] newTable = copy(table); boolean putable = true; for(int k=0;k<ph;++k)for(int l=0;l<pw;++l){ if(p[k][l]&&table[x-px+k][y-py+l]>0)putable=false; if(p[k][l])newTable[x-px+k][y-py+l]=num; } if(putable){ Parts tmp = ps.get(i); ps.remove(i); if(solve(ps,newTable,num+1)){ ps.add(i,tmp); return true; } ps.add(i,tmp); } } } return false; } int[][] copy(int[][] original){ int h = original.length; int w = original[0].length; int[][] mirror = new int[h][w]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)mirror[i][j]=original[i][j]; return mirror; } class Parts{ boolean[][] parts; int h, w; public Parts(boolean[][] p){ h = p.length; w = p[0].length; parts = new boolean[h][w]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)parts[i][j]=p[i][j]; } boolean[][][] getParts(){ boolean[][][] ps = new boolean[4][][]; ps[0] = new boolean[h][w]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)ps[0][i][j]=parts[i][j]; ps[1] = new boolean[w][h]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)ps[1][w-1-j][i]=parts[i][j]; ps[2] = new boolean[h][w]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)ps[2][h-1-i][w-1-j]=parts[i][j]; ps[3] = new boolean[w][h]; for(int i=0;i<h;++i)for(int j=0;j<w;++j)ps[3][j][h-1-i]=parts[i][j]; return ps; } } void show(boolean[][] p){ int h = p.length; int w = p[0].length; for(int i=0;i<h;++i){ for(int j=0;j<w;++j)System.out.print((p[i][j])?"x":" "); System.out.println(); } System.out.println(); } void show(int[][] p){ int h = p.length; int w = p[0].length; for(int i=0;i<h;++i){ for(int j=0;j<w;++j)System.out.print((char)p[i][j]); System.out.println(); } System.out.println(); } public static void main(String[] args) { new Choco().run();} }
チョコレートパズルの場合は次のような入力で動かせば
6 11 11
2 5
xxxxx
oooxo
2 4
xxxo
oxxx
4 2
xo
xx
xo
xx
3 3
oxx
xxo
oxx
2 5
xxooo
oxxxx
3 3
xxo
xoo
xxx
2 5
xxxxx
oooox
2 4
xxxo
xoxx
3 4
ooxo
xxxx
ooxo
3 3
oox
oxx
xxx
4 3
oxo
xxx
xoo
xoo
出力結果は
aaaaabccccc
dddabbbeeec
fdddbggehee
ffiibghhhhj
fiikkggghjj
ffiikkkkjjj
のようになる.
実装が適当だからか3秒以上計算にかかってしまう.