アルゴリズムの勉強をしています。
Aizu Online Judgeの8パズルでどうしてもTLEになってしまいます。
C#
1using System; 2using System.Linq; 3using System.Collections.Generic; 4 5public class Program{ 6 public static void Main(){ 7 var Board = new int[3, 3]; 8 for(int i=0; i<3; i++){ 9 var line = Console.ReadLine().Split().Select(int.Parse).ToArray(); 10 for(int j=0; j<3; j++){ 11 Board[i, j] = line[j]; 12 } 13 } 14 var Goal = new int[,]{ {1, 2, 3}, {4, 5, 6}, {7, 8, 0} }; 15 var StrGoal = ToStringForList(Goal); 16 var queue = new Queue<State>(); 17 var all_list = new List<string>(); 18 queue.Enqueue(new State{table = Board, cnt = 0}); 19 while(queue.Count()>0){ 20 var curr = queue.Dequeue(); 21 if(all_list.Contains(ToStringForList(curr.table)))continue; 22 else all_list.Add(ToStringForList(curr.table)); 23 if(ToStringForList(curr.table)==StrGoal){ 24 Console.WriteLine(curr.cnt); 25 break; 26 } 27 28 var Now = curr.GetPos(); 29 var cx = Now.X; 30 var cy = Now.Y; 31 var steps = new int[]{0, 1, 0, -1, 0}; 32 for(int i=0; i<4; i++){ 33 var nx = cx+steps[i+1]; 34 var ny = cy+steps[i]; 35 if(0<=nx && nx<Board.GetLength(1) && 0<=ny && ny<Board.GetLength(0)){ 36 var Nex = new Pos{Y = ny, X = nx}; 37 var NexMap = curr.Swap(Nex, Now); 38 queue.Enqueue(NexMap); 39 } 40 } 41 } 42 43 } 44 45 public static string ToStringForList(int[,] map){ 46 var ret=""; 47 for(int i=0; i<map.GetLength(0); i++){ 48 for(int j=0; j<map.GetLength(1); j++){ 49 ret+=map[i, j]; 50 } 51 } 52 return ret; 53 } 54} 55 56public struct Pos{ 57 public int X{set; get;} 58 public int Y{set; get;} 59} 60 61public struct State{ 62 public int cnt{set; get;} 63 public int[,] table{set; get;} 64 public Pos GetPos(){ 65 var retPos = new Pos{X = -1, Y = -1}; 66 for(int i=0; i<this.table.GetLength(0); i++){ 67 for(int j=0; j<this.table.GetLength(1); j++){ 68 if(this.table[i, j]==0){ 69 retPos.X = j; 70 retPos.Y = i; 71 } 72 } 73 } 74 return retPos; 75 } 76 77 public State Swap(Pos pre, Pos nex){ 78 var _tmp = this.table.Clone() as int[,]; 79 var _cnt = this.cnt; 80 _tmp[nex.Y, nex.X] = this.table[pre.Y, pre.X]; 81 _tmp[pre.Y, pre.X] = this.table[nex.Y, nex.X]; 82 return new State{cnt = _cnt+=1, table = _tmp}; 83 } 84}
最短手数を求めよとのことで幅優先探索を使っています。
このコードだとcase15でTLEになります。
ほかの方の提出して得るコードをみるとなにか謎手法を用いているように思われ、解読できませんでした。ただ中には同じようにBFSを使っているものもあり、書き方のせいなのかなとも思います。
ご指摘よろしくおねがいします。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2017/07/28 10:28