結果
| 問題 | No.460 裏表ちわーわ |
| ユーザー |
 明智重蔵
|
| 提出日時 | 2016-12-23 07:33:07 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 223 ms / 2,000 ms |
| コード長 | 6,367 bytes |
| コンパイル時間 | 1,146 ms |
| コンパイル使用メモリ | 114,240 KB |
| 実行使用メモリ | 31,340 KB |
| 最終ジャッジ日時 | 2024-12-14 15:16:25 |
| 合計ジャッジ時間 | 4,006 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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("5 5");WillReturn.Add("0 0 1 1 1");WillReturn.Add("0 0 1 1 1");WillReturn.Add("1 1 0 1 1");WillReturn.Add("1 1 1 0 0");WillReturn.Add("1 1 1 0 0");//2}else if (InputPattern == "Input2") {WillReturn.Add("4 4");WillReturn.Add("0 0 0 0");WillReturn.Add("0 1 1 0");WillReturn.Add("0 1 1 0");WillReturn.Add("0 0 0 0");//16}else if (InputPattern == "Input3") {WillReturn.Add("8 5");WillReturn.Add("0 0 1 1 1");WillReturn.Add("0 0 1 1 1");WillReturn.Add("0 1 0 0 1");WillReturn.Add("1 0 0 1 0");WillReturn.Add("1 1 1 0 0");WillReturn.Add("1 0 1 0 1");WillReturn.Add("0 1 0 0 1");WillReturn.Add("0 0 1 1 1");//5}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}static int UB_X;static int UB_Y;struct JyoutaiDef{internal int CurrX;internal int CurrY;internal int Cost;internal bool[,] MasuArr;}static void Main(){List<string> InputList = GetInputList();int[] wkArr = { };Action<string> SplitAct = pStr =>wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();SplitAct(InputList[0]);int M = wkArr[0], N = wkArr[1];UB_X = N - 1;UB_Y = M - 1;bool[,] mQuestionArr = new bool[UB_X + 1, UB_Y + 1];for (int I = 1; I <= InputList.Count - 1; I++) {SplitAct(InputList[I]);for (int J = 0; J <= wkArr.GetUpperBound(0); J++) {mQuestionArr[J, I - 1] = (wkArr[J] == 1);}}var Stk = new Stack<JyoutaiDef>();JyoutaiDef WillPush;WillPush.CurrX = WillPush.CurrY = 0;WillPush.Cost = 0;WillPush.MasuArr = mQuestionArr;Stk.Push(WillPush);int AnswerCost = int.MaxValue;bool FoundAnswer = false;while (Stk.Count > 0) {JyoutaiDef Popped = Stk.Pop();if (IsOK(Popped.MasuArr)) {FoundAnswer = true;AnswerCost = Popped.Cost;continue;}//下限値枝切りif (AnswerCost <= Popped.Cost) continue;if (Popped.CurrY == UB_Y + 1) {continue;}//次の座標を設定WillPush.CurrY = Popped.CurrY;WillPush.CurrX = Popped.CurrX + 1;if (WillPush.CurrX == UB_X + 1) {WillPush.CurrY++;WillPush.CurrX = 0;}bool WillPushHanten = false; //反転させるケースbool WillPushNonHanten = false; //反転させないケースif (Popped.CurrY == 0) { //Y座標が0の場合WillPushHanten = WillPushNonHanten = true;}else { //Y座標が1以上の場合var wkList = new List<bool>();//X=UB_Xなら、真上と左上if (Popped.CurrX == UB_X) {wkList.AddRange(DeriveBoolList(Popped.MasuArr, Popped.CurrX, Popped.CurrY - 1));wkList.AddRange(DeriveBoolList(Popped.MasuArr, Popped.CurrX - 1, Popped.CurrY - 1));}else { //X<UB_Xなら、左上wkList.AddRange(DeriveBoolList(Popped.MasuArr, Popped.CurrX - 1, Popped.CurrY - 1));}if (wkList.Count == 0) {WillPushHanten = WillPushNonHanten = true;}else if (wkList.TrueForAll(A => A)) { //全部1の場合WillPushHanten = true;}else if (wkList.TrueForAll(A => A == false)) { //全部0の場合WillPushNonHanten = true;}}if (WillPushHanten) { //反転させるケースをPushWillPush.Cost = Popped.Cost + 1;WillPush.MasuArr = (bool[,])Popped.MasuArr.Clone();HantenSyori(WillPush.MasuArr, Popped.CurrX, Popped.CurrY);Stk.Push(WillPush);}if (WillPushNonHanten) { //反転させないケースをPushWillPush.Cost = Popped.Cost;WillPush.MasuArr = Popped.MasuArr;Stk.Push(WillPush);}}if (FoundAnswer)Console.WriteLine(AnswerCost);else Console.WriteLine("Impossible");}//終了判定static bool IsOK(bool[,] pMasuArr){foreach (bool EachBool in pMasuArr) {if (EachBool) return false;}return true;}//指定した座標のBool型のListを返すstatic List<bool> DeriveBoolList(bool[,] pMasuArr, int pX, int pY){if (pX < 0 || UB_X < pX) return new List<bool>();if (pY < 0 || UB_Y < pY) return new List<bool>();return new List<bool>() { pMasuArr[pX, pY] };}//押したマスと8近傍の、座標を反転static void HantenSyori(bool[,] pMasuArr, int pX, int pY){MasuHanten(pMasuArr, pX - 1, pY - 1);MasuHanten(pMasuArr, pX - 1, pY);MasuHanten(pMasuArr, pX - 1, pY + 1);MasuHanten(pMasuArr, pX, pY - 1);MasuHanten(pMasuArr, pX, pY);MasuHanten(pMasuArr, pX, pY + 1);MasuHanten(pMasuArr, pX + 1, pY - 1);MasuHanten(pMasuArr, pX + 1, pY);MasuHanten(pMasuArr, pX + 1, pY + 1);}//指定マスの0と1の反転static void MasuHanten(bool[,] pMasuArr, int pX, int pY){if (pX < 0 || UB_X < pX) return;if (pY < 0 || UB_Y < pY) return;pMasuArr[pX, pY] = !pMasuArr[pX, pY];}}