問題の分析
N×MのテーブルがAntimatterとMatterで埋められています。
Antimatterの上に1×Kの大きさのアメーバを配置する方法は全部で何通りあるかを答えなさい。
アメーバはテーブルからはみ出したり、アメーバの下にMatterがきたりしてはいけません。
制約はN,M<50。
方針
問題のサイズが小さいのでとにかく全通り調べればOKです。
ただし、アメーバの大きさが1×1の場合、1×2以上の大きさの場合と同じ数え方では答えが2倍になってしまうので注意。
ソースコード
using System; using System.Collections.Generic; using System.Text; public class AmoebaDivTwo { public int count(String[] table, int K) { int w = table[0].Length; int h = table.Length; int cnt = 0; for (int x = 0; x < w - K + 1; x++) for (int y = 0; y < h; y++) { bool flg; flg = true; for (int k = x; k < x + K; k++) if (table[y][k].Equals('M')) { flg = false; break; } if (flg) cnt++; } for(int x = 0;x < w;x++) for (int y = 0; y < h - K + 1; y++) { bool flg = true; for (int k = y; k < y + K; k++) if (table[k][x].Equals('M')) { flg = false; break; } if (flg) cnt++; } if (K == 1) cnt /= 2; return cnt; } }