結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー 14番
提出日時 2016-05-05 04:46:50
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 4,295 bytes
コンパイル時間 900 ms
コンパイル使用メモリ 113,284 KB
実行使用メモリ 26,348 KB
最終ジャッジ日時 2024-10-05 09:26:16
合計ジャッジ時間 2,522 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
 
class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        Panel[,] map = new Panel[4,4];
        for(int i=0; i<4; i++) {
            int[] inpt = Reader.GetInt();
            for(int j=0; j<4; j++) {
                map[i,j] = new Panel(inpt[j]);
            }
        }
        int ans = this.GetAns(map);
        Console.WriteLine((ans>=0)?"Yes":"No");
    }
    
    public int GetAns(Panel[,] target) {
        int x = 0;
        int y = 0;
        for(int i=0; i<target.GetLength(0); i++) {
            for(int j=0; j<target.GetLength(0); j++) {
                if(target[i,j].Num == 0) {
                    x = j;
                    y = i;
                    break;
                }
            }
        }
        
        if(this.IsGoal(target)) {
            return 0;
        }
        
        int ans = int.MaxValue;
        List<int[]> slid = new List<int[]>();
        if(x > 0 && target[y, x-1].CanSlide) {
            slid.Add(new int[]{y, x-1});;
        }
        if(x < target.GetLength(1) - 1 && target[y, x+1].CanSlide) {
            slid.Add(new int[]{y, x+1});;
        }
        if(y > 0 && target[y-1, x].CanSlide) {
            slid.Add(new int[]{y-1, x});;
        }
        if(y < target.GetLength(0)-1 && target[y+1, x].CanSlide) {
            slid.Add(new int[]{y+1, x});;
        }
        foreach (int[] pos in slid)
        {
            int nextX = pos[1];
            int nextY = pos[0];
            Panel[,] subMap = this.DuplicateMap(target);
            subMap[y, x].Num = target[nextY, nextX].Num;
            subMap[y, x].CanSlide = false;
            subMap[nextY, nextX].Num = 0;
            int ret = this.GetAns(subMap);
            if(ret >= 0) {
                ans = Math.Min(ans, ret + 1);
            }
        }
        if(ans == int.MaxValue) {
            ans = -1;
        }
        return ans;
        
    }
    
    private bool IsGoal(Panel[,] target) {
        int idx = 1;
        for(int i=0; i<target.GetLength(0); i++) {
            for(int j=0; j<target.GetLength(1); j++) {
                if(target[i,j].Num != idx) {
                    return false;
                }
                if(idx == 15) {
                    idx = 0;
                } else
                {
                    idx++;
                }
            }
        }
        return true;
    }
    private Panel[,] DuplicateMap(Panel[,] src) {
        Panel[,] ret = new Panel[src.GetLength(0),src.GetLength(1)];
        for(int i=0; i<src.GetLength(0); i++) {
            for(int j=0; j<src.GetLength(1); j++) {
                ret[i,j] = src[i,j].Duplicate();
            }
        }
        return ret;
    }
    
    public class Panel {
        public int Num;
        public bool CanSlide = true;
        public Panel(int num) {
            this.Num = num;
        }
        
        public Panel Duplicate() {
            Panel newP = new Panel(this.Num);
            newP.CanSlide = this.CanSlide;
            return newP;
        }
    }
    
    


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


1 2 3 4
5 6 7 8
9 10 12 15
13 14 11 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();
            }
        }
        public static int[] GetInt(char delimiter = ' ', bool trim = false)
        {
            string inptStr = ReadLine();
            if (trim)
            {
                inptStr = inptStr.Trim();
            }
            string[] inpt = inptStr.Split(delimiter);
            int[] ret = new int[inpt.Length];
            for (int i = 0; i < inpt.Length; i++)
            {
                ret[i] = int.Parse(inpt[i]);
            }
            return ret;
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0