AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC224-D 8 Puzzle on Graph
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("5");
WillReturn.Add("1 2");
WillReturn.Add("1 3");
WillReturn.Add("1 9");
WillReturn.Add("2 9");
WillReturn.Add("3 9");
WillReturn.Add("3 9 2 4 5 6 7 8");
//5
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("1 2");
WillReturn.Add("1 3");
WillReturn.Add("1 9");
WillReturn.Add("2 9");
WillReturn.Add("3 9");
WillReturn.Add("1 2 3 4 5 6 7 8");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("12");
WillReturn.Add("8 5");
WillReturn.Add("9 6");
WillReturn.Add("4 5");
WillReturn.Add("4 1");
WillReturn.Add("2 5");
WillReturn.Add("8 9");
WillReturn.Add("2 1");
WillReturn.Add("3 6");
WillReturn.Add("8 7");
WillReturn.Add("6 5");
WillReturn.Add("7 4");
WillReturn.Add("2 3");
WillReturn.Add("1 2 3 4 5 6 8 7");
//-1
}
else if (InputPattern == "Input4") {
WillReturn.Add("12");
WillReturn.Add("6 5");
WillReturn.Add("5 4");
WillReturn.Add("4 1");
WillReturn.Add("4 7");
WillReturn.Add("8 5");
WillReturn.Add("2 1");
WillReturn.Add("2 5");
WillReturn.Add("6 9");
WillReturn.Add("3 6");
WillReturn.Add("9 8");
WillReturn.Add("8 7");
WillReturn.Add("3 2");
WillReturn.Add("2 3 4 6 1 9 7 8");
//16
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int mM;
// 隣接リスト
static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();
static int[] mBanArr;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
mM = int.Parse(InputList[0]);
foreach (string EachStr in InputList.Skip(1).Take(mM)) {
SplitAct(EachStr);
int FromNode = wkArr[0] - 1;
int ToNode = wkArr[1] - 1;
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<int>();
}
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<int>();
}
mToNodeListDict[FromNode].Add(ToNode);
mToNodeListDict[ToNode].Add(FromNode);
}
int[] PArr = InputList.Last().Split(' ').Select(pX => int.Parse(pX)).ToArray();
mBanArr = new int[9];
for (int I = 0; I <= PArr.GetUpperBound(0); I++) {
mBanArr[PArr[I] - 1] = I + 1;
}
ExecBFS();
}
struct JyoutaiDef
{
internal int[] BanArr;
internal int Level;
}
static void ExecBFS()
{
var Que = new Queue<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.BanArr = mBanArr;
WillEnqueue.Level = 0;
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<long>();
VisitedSet.Add(GetHash(mBanArr));
while (Que.Count > 0) {
JyoutaiDef Dequeued = Que.Dequeue();
if (IsClear(Dequeued.BanArr)) {
Console.WriteLine(Dequeued.Level);
return;
}
int Ind0 = Array.IndexOf(Dequeued.BanArr, 0);
if (mToNodeListDict.ContainsKey(Ind0)) {
foreach (int EachFromNode in mToNodeListDict[Ind0]) {
WillEnqueue.BanArr = (int[])Dequeued.BanArr.Clone();
int FromNum = Dequeued.BanArr[EachFromNode];
WillEnqueue.BanArr[Ind0] = FromNum;
WillEnqueue.BanArr[EachFromNode] = 0;
WillEnqueue.Level = Dequeued.Level + 1;
long Hash = GetHash(WillEnqueue.BanArr);
if (VisitedSet.Add(Hash)) {
Que.Enqueue(WillEnqueue);
}
}
}
}
Console.WriteLine(-1);
}
// クリア判定
static bool IsClear(int[] pArr)
{
for (int I = 0; I <= 7; I++) {
if (pArr[I] != I + 1) return false;
}
return true;
}
// ハッシュ値を求める
static long GetHash(int[] pArr)
{
long WillReturn = 0;
foreach (int EachInt in pArr) {
WillReturn += EachInt;
WillReturn *= 10;
}
return WillReturn;
}
}
解説
ナイーブに幅優先探索してます。