学内プロコン(15/03/26)

procon.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    // ref: https://github.com/OCTPC/miniprocon/blob/master/miniprocon002/regulation.md
    static void Main(string[] args)
    {
        string[] str = Console.ReadLine().Split(' ');
        long n = long.Parse(str[0]);
        long m = long.Parse(str[1]);

        var map = new bool[m, n];
        var memox = new int[m, n];
        var memoy = new int[m, n];

        for (int i = 0; i < n; i++)
        {
            int begin = 0, count = 0;
            string s = Console.ReadLine();
            for (int j = 0; j < m; j++)
            {
                map[j, i] = s[j] == '#';
                // 読みながらxカウント
                if (map[j, i])
                {
                    count++;
                    if (j < m - 1) continue; // 端だったら強制カウントさせる
                }

                for (int k = j; k >= begin; k--)
                    memox[k, i] = begin + count - k;
                begin = j + 1;
                count = 0;
            }
        }

        //// xカウント
        //for (int i = 0; i < n; i++)
        //{
        //    int begin = 0, count = 0;
        //    while (begin < m)
        //    {
        //        for (int j = begin; j < m; j++)
        //        {
        //            if (map[j, i])
        //            {
        //                count++;
        //                if (j < m - 1) continue;
        //            }

        //            for (int k = j; k >= begin; k--)
        //                memox[k, i] = begin + count - k;
        //            begin = j + 1;
        //            count = 0;
        //        }
        //    }
        //}

        // yカウント
        for (int i = 0; i < m; i++)
        {
            int begin = 0, count = 0;
            for (int j = begin; j < n; j++)
            {
                if (map[i, j])
                {
                    count++;
                    if (j < n - 1) continue;
                }

                for (int k = j; k >= begin; k--)
                    memoy[i, k] = begin + count - k;
                begin = j + 1;
                count = 0;
            }
        }

        int ans = 0;
        for (int y = 0; y < n - 2; y++)
            for (int x = 0; x < m - 2; x++)
            {
                if (!map[x, y]) continue;
                if (memox[x, y] < 3 || memoy[x, y] < 3) continue;

                int tilx = x + memox[x, y]; // 可能性のある右端まで
                int tily = y + memoy[x, y]; // 可能性のある下っ端まで
                for (int i = x + 2; i < tilx; i++)
                {
                    if (memoy[i, y] < 3) continue;

                    for (int j = y + 2; j < tily; j++)
                    {
                        if (!map[i, j]) break;// 右の辺が絶たれていたら打ち切る (テストケースで発見できなかったバグ)
                        if (memox[x, j] >= i - x + 1) ans++;
                    }
                }
            }

        Console.WriteLine(ans);
    }
}