[Algorithm]ゲームボードをかぶせる

28842 ワード
鐘万北 フルナビゲーション algospot テキストリンク

1.問題の解釈


白いパネルの数を3マスLブロックでカバーします.
オーバーラップ不可
入力
C(テストケース)
H(縦)W(横)
#(黒い格子).(スペース)
しゅつりょく
カバープレート数

2.アイデア


💡 Lブロックを回転させる場合、4種類の形状を選択できます
💡 白と黒を分け、カバーできない場所と位置をLブロックで区切る
💡 組合せを使用して解く:再帰関数かいきかんすう

3.解答


1)L形状が使用可能である場合、アレイとして宣言する
int coverType[][][] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};
2)Boardの左上からナビゲーションを開始し、Boardが0であれば空白(重複防止のため)
for(int i=0; i<board.length; ++i) {
			for(int j=0; j<board[i].length; ++j) {
				if(board[i][j] == 0) {
					y = i;
					x = j;
					break;
				}
			}
			if(y != -1)
				break;
		}
3)空白の白い格子の周囲に3格子を確保し、L形状を加えてカウントした後、再度減算する
for(int type =0; type<4; type++) {
			if(set(board,y,x,type,1))
				ret+=cover(board);
			set(board,y,x,type,-1);
	}

4.コード

import java.io.*;

public class BoardCover {
	static int c,w,h;
	static int coverType[][][] = {
			{{0,0},{1,0},{0,1}},
			{{0,0},{0,1},{1,1}},
			{{0,0},{1,0},{1,1}},
			{{0,0},{1,0},{1,-1}}
			};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		c = Integer.parseInt(br.readLine());
		int result[] = new int[c];
		
		for(int i=0; i<c; i++) {
			String s[] = br.readLine().split(" ");
			h = Integer.parseInt(s[0]);
			w = Integer.parseInt(s[1]);
			int board[][] = new int[h][w];
			
			for(int k=0; k<h; k++) {
				String str = br.readLine();
				for(int j=0; j<w; j++) {
					board[i][j] = str.charAt(j) == '#'? 1:0;
				}
			}
			
			result[i] = cover(board);
		}
		
		for(int i=0; i<c; i++)
			System.out.println(result[i]);
	
	}
	
	public static boolean set(int board[][],int y, int x, int type, int delta) {
		boolean ok = true;
		
		for(int i=0; i<3; ++i) {
			int ny = y + coverType[type][i][0];
			int nx = x + coverType[type][i][1];
			
			if(ny<0 || ny>=board.length || nx<0 || nx>= board[0].length)
				ok = false;
			else if((board[ny][nx] += delta) > 1)
				ok = false;
		}
		
		return ok;
	}
	
	public static int cover(int board[][]) {
		int y = -1, x = -1;
		
		for(int i=0; i<board.length; ++i) {
			for(int j=0; j<board[i].length; ++j) {
				if(board[i][j] == 0) {
					y = i;
					x = j;
					break;
				}
			}
			if(y != -1)
				break;
		}
		
		if(y == -1) 
			return 1;
		
		int ret = 0;
		
		for(int type =0; type<4; type++) {
			if(set(board,y,x,type,1))
				ret+=cover(board);
			set(board,y,x,type,-1);
		}
		
		return ret;
	}
}

5.結果



どうしてだめなの...
Introduction to NLP (Wk.6)
docker-compose.yml詳細