結果

問題 No.460 裏表ちわーわ
コンテスト
ユーザー 14番
提出日時 2016-12-11 03:42:21
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 3,691 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,075 ms
コンパイル使用メモリ 116,476 KB
実行使用メモリ 294,228 KB
最終ジャッジ日時 2024-11-29 03:00:52
合計ジャッジ時間 74,826 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 1 TLE * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

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

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inp = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int h = inp[0];
        int w = inp[1];
        this.Map = new bool[h][];
        bool[][] goal = new bool[h][];

        for (int i = 0; i < h; i++)
        {
            Map[i] = Reader.ReadLine().Split(' ').Select(a => a[0] == '1').ToArray();
            goal[i] = new bool[w];
        }

        this.mapKey = GetKey(this.Map);

        Task goalTask = new Task(goal, GetKey(goal), 0);
        SetDic(goalTask);
        if (dic.ContainsKey(mapKey))
        {
            Console.WriteLine(dic[mapKey].Step);
        }
        else
        {
            Console.WriteLine("Impossible");
        }

    }

    private void SetDic(Task t)
    {
        if (t.Key == this.mapKey)
        {
            return;
        }
        if (t.Step > 16)
        {
            return;
        }
        

        for (int i = 0; i < t.Map.Length; i++)
        {
            for (int j = 0; j < t.Map[0].Length; j++)
            {
                bool[][] nextMap = this.Conv(t.Map, i, j);
                Task nextTask = new Task(nextMap, GetKey(nextMap), t.Step + 1);
                if (dic.ContainsKey(nextTask.Key) && dic[nextTask.Key].Step <= nextTask.Step)
                {
                    continue;
                }
                dic[nextTask.Key] = nextTask;
                SetDic(nextTask);
            }
        }
    }

    private Dictionary<ulong, Task> dic = new Dictionary<ulong, Task>();
    private ulong mapKey;

    public struct Task
    {
        public bool[][] Map;
        public ulong Key;
        public int Step;
        public Task(bool[][] mp, ulong key, int step)
        {
            this.Map = mp;
            this.Key = key;
            this.Step = step;
        }
    }

    private ulong GetKey(bool[][] src)
    {
        ulong ret = 0;
        for (int i = 0; i < src.Length; i++)
        {
            for (int j = 0; j < src[i].Length; j++)
            {
                if (src[i][j])
                {
                    int idx = (i * src[i].Length) + j;
                    ret += (ulong)(1<<idx);
                }
            }
        }
        return ret;
    }
    private bool[][] Conv(bool[][] src, int row, int col)
    {
        bool[][] ret = new bool[src.Length][];
        for (int i = 0; i < src.Length; i++)
        {
            ret[i] = new bool[src[i].Length];
            for (int j = 0; j < src[i].Length; j++)
            {
                if (i >= row - 1 && i <= row + 1 && j >= col - 1 && j <= col + 1)
                {
                    ret[i][j] = !src[i][j];
                }
                else
                {
                    ret[i][j] = src[i][j];
                }
            }
        }
        return ret;
    }

    private bool[][] Map;


    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"

   
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0






";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0