読者です 読者をやめる 読者になる 読者になる

日々精進

新しく学んだことを書き留めていきます

SRM493 Div2 Easy

問題の分析
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[,] tbl = new int[w + K, h + K];
        for(int i = 0;i < w;i++)
            for(int j = 0;j < h;j++)
                if(table[j][i].Equals('A'))
                    tbl[i, j] = 1;
 
 
        int cnt = 0;
        for(int x = 0;x < w;x++)
            for(int y = 0;y < h;y++)
            {
                bool flg;
                flg = true;
                for (int k = x; k < x + K; k++)
                    if (tbl[k, y].Equals(0))
                    {
                        flg = false;
                        break;
                    }
                if (flg) cnt++;
 
 
                if (!K.Equals(1))
                {
                    flg = true;
                    for (int k = y; k < y + K; k++)
                        if (tbl[x, k].Equals(0))
                        {
                            flg = false;
                            break;
                        }
                    if (flg) cnt++;
                }
            }
        return cnt;
    }
}


他の人のソースコードは下のようになっていました。
確かにTableを広げるより探索範囲を狭めた方が簡単な気がします。
>|cs|
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;
}
}
|