AOJ 0760 コイン集め 2

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("1 1");
            WillReturn.Add("#");
            //1 0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 5");
            WillReturn.Add("#####");
            WillReturn.Add("####.");
            WillReturn.Add("###..");
            WillReturn.Add("##...");
            WillReturn.Add("#....");
            //13 12
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 40");
            WillReturn.Add("..........##########..........##########");
            //19 21
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("7 1");
            WillReturn.Add("#");
            WillReturn.Add("#");
            WillReturn.Add("#");
            WillReturn.Add("#");
            WillReturn.Add("#");
            WillReturn.Add("#");
            WillReturn.Add("#");
            //1 6
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("5 5");
            WillReturn.Add(".###.");
            WillReturn.Add("...##");
            WillReturn.Add("..##.");
            WillReturn.Add(".##..");
            WillReturn.Add("##...");
            //11 14
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("10 40");
            WillReturn.Add("........................................");
            WillReturn.Add("..######.....####.....#####.....####....");
            WillReturn.Add(".....#......#....#......#......#........");
            WillReturn.Add(".....#......#....#......#......#........");
            WillReturn.Add(".....#......#....#......#......#........");
            WillReturn.Add(".....#......#....#......#......#..####..");
            WillReturn.Add("..#..#......#....#......#......#....#...");
            WillReturn.Add("..#..#......#....#......#......#....#...");
            WillReturn.Add("...##........####.....#####.....####....");
            WillReturn.Add("........................................");
            //104 296
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[,] BanArr = CreateBanArr(InputList.Skip(1));
        int UB_X = BanArr.GetUpperBound(0);
        int UB_Y = BanArr.GetUpperBound(1);

        int TotalScore = (UB_X + 1) * (UB_Y + 1);

        // 表の枚数[X座標]
        int[] DefaultOmoteCntArr = new int[UB_X + 1];

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == '#') {
                    DefaultOmoteCntArr[LoopX]++;
                }
            }
        }

        //for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
        //    Console.WriteLine("DefaultOmoteCntArr[{0}]={1}", LoopX, DefaultOmoteCntArr[LoopX]);
        //}

        // 先手のスコアのList
        var SenteScoreList = new List<int>();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            int[] CurrOmoteCntArr = new int[UB_X + 1];
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                if (BanArr[LoopX, LoopY] == '#') {
                    CurrOmoteCntArr[LoopX] = DefaultOmoteCntArr[LoopX] - 1;
                }
                else {
                    CurrOmoteCntArr[LoopX] = DefaultOmoteCntArr[LoopX] + 1;
                }
            }
            CurrOmoteCntArr = CurrOmoteCntArr.OrderByDescending(pX => pX).ToArray();
            int Height = UB_Y + 1;
            CurrOmoteCntArr[0] = Height - CurrOmoteCntArr[0];

            SenteScoreList.Add(CurrOmoteCntArr.Sum());
        }
        int SenteScore = SenteScoreList.Max();
        int GoteScore = TotalScore - SenteScore;
        Console.WriteLine("{0} {1}", SenteScore, GoteScore);
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

解説

表の枚数[X座標]を最初に求めてから、
先手が選ぶY座標を全探索し、
そのY座標ごとの後手が選ぶX座標を求めてます。