明治ブラックチョコパズル

研究室にあったパズルを崩したら戻せなくなったので仕方なく全探索のプログラムを書いた.

明治ブラックチョコパズル

明治ブラックチョコパズル


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秒以上計算にかかってしまう.