結果
問題 | No.228 ゆきこちゃんの 15 パズル |
ユーザー |
![]() |
提出日時 | 2017-10-01 22:52:21 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 4,359 bytes |
コンパイル時間 | 994 ms |
コンパイル使用メモリ | 111,200 KB |
実行使用メモリ | 18,048 KB |
最終ジャッジ日時 | 2024-11-15 21:49:01 |
合計ジャッジ時間 | 2,312 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ProgrammingContest { class MainClass { Scanner sc; static void Main(string[] args) { new MainClass().Solve(); } const bool DEBUG = false; // TODO: must check!! void Solve() { if (DEBUG) { string backPath = ".."; char dirSep = System.IO.Path.DirectorySeparatorChar; string inFilePath = backPath + dirSep + backPath + dirSep + "in.txt"; sc = new Scanner(new System.IO.StreamReader(inFilePath)); } else { sc = new Scanner(); } for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { a[i, j] = abuf[i, j] = sc.NextInt; perfect[i, j] = (i * 4 + j + 1) % 16; } } bool ok = false; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { ok |= dfs(i, j); Array.Copy(abuf, a, a.Length); } } Console.WriteLine(ok ? "Yes" : "No"); } bool dfs(int x, int y) { //outAr(a); bool res = false; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (inside(nx, ny) && a[nx, ny] == perfect[x, y] && (a[x, y] == 0 || a[nx, ny] == 0)) { int buf = a[x, y]; a[x, y] = a[nx, ny]; a[nx, ny] = buf; res |= dfs(nx, ny); } } return res || check(a); } int[,] a = new int[4, 4]; int[,] abuf = new int[4, 4]; int[,] perfect = new int[4, 4]; int[] dx = { 0, -1, 0, 1}; int[] dy = { -1, 0, 1, 0}; void outAr(int[,] ar) { Console.WriteLine(); for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { Console.Write(a[i, j] + " "); } Console.WriteLine(); } } bool inside(int x, int y) { return 0 <= x && x < 4 && 0 <= y && y < 4; } bool check(int[,] ar) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (perfect[i, j] != ar[i, j]) { return false; } } } return true; } } class Scanner { Queue<String> buffer; char[] sep; System.IO.TextReader reader; public Scanner(System.IO.TextReader reader = null) { this.buffer = new Queue<string>(); this.sep = new char[] { ' ' }; this.reader = (reader ?? Console.In); } private void CheckBuffer() { if (this.buffer.Count == 0) { String[] sreArray = this.reader.ReadLine().Split(this.sep); foreach (String elStr in sreArray) { this.buffer.Enqueue(elStr); } } } public String Next { get { this.CheckBuffer(); return this.buffer.Dequeue(); } } public int NextInt { get { return int.Parse(this.Next); } } public double NextDouble { get { return double.Parse(this.Next); } } public long NextLong { get { return long.Parse(this.Next); } } public bool IsEmpty { get { this.CheckBuffer(); return this.buffer.Count == 0; } } } }