uzutaka's notes

web系ソフトウェア開発,プログラミングなどについてまとめます.

TopCoder SRM 593 DIV 1 EASY HexagonalBoard をC#で解く

プラグインにTZTesterのC#版を使っていますが、新しくできたGreedが使いやすく人気のようです。

https://github.com/shivawu/topcoder-greed

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

public class HexagonalBoard
{
    int N;
    int[,] colors;
    int[] dx = { 0,  1,  1,  0, -1, -1 };
    int[] dy = { -1, -1,  0,  1,  1,  0 };
    string[] board;
    int res;

    public int minColors(string[] _board)
    {
        board = _board;
        N = board.Length;
        colors = new int[N, N];
        res = 0;
        
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (board[i][j] == 'X' && colors[i, j] == 0)
                {
                    Dfs(j, i, 1);
                }
            }
        }
        
        return res;
    }

    void Dfs(int x, int y, int c)
    {
        colors[y, x] = c;
        res = Math.Max(res, 1);
        for (int i = 0; i < dx.Length; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[ny][nx] != 'X')
            {
                continue;
            }
            if (colors[ny, nx] == c)
            {
                res = 3;
            }
            if (colors[ny, nx] == 0)
            {
                res = Math.Max(res, 2);
                Dfs(nx, ny, -c);
            }
        }
    }

    // BEGIN CUT HERE
    public void run_test(int Case)
    {
        if ((Case == -1) || (Case == 0))
            test_case_0();
        if ((Case == -1) || (Case == 1))
            test_case_1();
        if ((Case == -1) || (Case == 2))
            test_case_2();
        if ((Case == -1) || (Case == 3))
            test_case_3();
    }

    void verify_case(int Case, int Expected, int Received)
    {
        Console.Write("Test Case #" + Case + "...");
        if (Expected == Received)
            Console.Write("PASSED\n");
        else
        {
            Console.Write("FAILED\n");
            Console.Write("\tExpected: \"" + Expected + "\"\n");
            Console.Write("\tReceived: \"" + Received + "\"\n");
        }
    }

    private void test_case_0()
    {
        string[] Arg0 =
            {"---",
            "---",
            "---"
        };
        int Arg1 = 0;
        verify_case(0, Arg1, minColors(Arg0));
    }

    private void test_case_1()
    {
        string[] Arg0 =
            {"-X--",
            "---X",
            "----",
            "-X--"
        };
        int Arg1 = 1;
        verify_case(1, Arg1, minColors(Arg0));
    }

    private void test_case_2()
    {
        string[] Arg0 =
            {"XXXX",
            "---X",
            "---X",
            "---X"
        };
        int Arg1 = 2;
        verify_case(2, Arg1, minColors(Arg0));
    }

    private void test_case_3()
    {
        string[] Arg0 =
            {"XX-XX--",
            "-XX-XXX",
            "X-XX--X",
            "X--X-X-",
            "XX-X-XX",
            "-X-XX-X",
            "-XX-XX-"
        };
        int Arg1 = 3;
        verify_case(3, Arg1, minColors(Arg0));
    }
    // END CUT HERE


    // BEGIN CUT HERE
    public static void Main()
    {
        try
        {
            HexagonalBoard ___test = new HexagonalBoard();
            ___test.run_test(-1);
        }
        catch (Exception e)
        {
            // Console.WriteLine(e.StackTrace);
            Console.WriteLine(e.ToString());
        }
    }
    // END CUT HERE
}