fork download 
  1. /*
  2.  * A* - Wikipedia
  3.  * http://j...content-available-to-author-only...a.org/wiki/A*
  4.  *
  5.  * A*探索アルゴリズムの再現
  6.  *
  7.  */
  8.  
  9. import java.util.*;
  10. import java.lang.*;
  11. import java.io.*;
  12.  
  13. class Ideone
  14. {
  15. 	public static void main (String[] args) throws java.lang.Exception
  16. 	{
  17.  
  18. 		Scanner sc = new Scanner(System.in);
  19. 		final int w = sc.nextInt();
  20. 		final int h = sc.nextInt();
  21. 		Node start = null;
  22. 		Node goal = null;
  23. 		int[][] map = new int[h][w];
  24. 		for (int y = 0; y < h; y++)
  25. 		{
  26. 			for (int x = 0; x < w; x++)
  27. 			{
  28. 				int f = sc.nextInt();
  29. 				if (f < 3)
  30. 				{
  31. 					if (f == 1)
  32. 					{
  33. 						start = new Node(x, y);
  34. 					}
  35. 					else if (f == 2)
  36. 					{
  37. 						goal = new Node(x, y);
  38. 					}
  39. 					map[y][x] = 0;
  40. 				}
  41. 				else
  42. 				{
  43. 					map[y][x] = 3;
  44. 				}
  45. 			}
  46. 		}
  47. 		if (start == null || goal == null) throw new Exception("input error");
  48.  
  49. 		HashMap<Node, Node> open = new HashMap<Node, Node>();
  50. 		HashMap<Node, Node> close = new HashMap<Node, Node>();
  51.  
  52. 		start.setFStar(distance(start, goal));
  53. 		open.put(start, start);
  54.  
  55. 		for (;;)
  56. 			{
  57. 			Node minf = null;
  58. 			for (Node node : open.values())
  59. 			{
  60. 				if (minf != null)
  61. 				{
  62. 					if (node.getFStar() >= minf.getFStar())
  63. 					{
  64. 						continue;
  65. 					}
  66. 				}
  67. 				minf = node;
  68. 			}
  69. 			if (minf == null)
  70. 			{
  71. 				System.out.println("failed");
  72. 				System.exit(0);
  73. 			}
  74. 			if (goal.equals(minf))
  75. 			{
  76. 				break;
  77. 			}
  78. 			open.remove(minf);
  79. 			close.put(minf, minf);
  80.  
  81. 			HashSet<Node> ms = new HashSet<Node>();
  82. 			for (int dy = -1; dy <= 1; dy++)
  83. 			{
  84. 				for (int dx = -1; dx <= 1; dx++)
  85. 				{
  86. 					if ((dx != 0 && dy != 0) || (dx == dy)) continue;
  87. 					int tx = dx + minf.x;
  88. 					int ty = dy + minf.y;
  89. 					if (tx < 0 || tx >= w || ty < 0 || ty >= h) continue;
  90. 					if (map[ty][tx] != 0) continue;
  91. 					Node m = new Node(tx, ty);
  92. 					ms.add(m);
  93. 				}
  94. 			}
  95.  
  96. 			double hstarN = distance(minf, goal);
  97. 			double gstarN = minf.getFStar() - hstarN;
  98. 			double cost = 1;
  99. 			for (Node m : ms)
  100. 			{
  101. 				double hstarM = distance(m, goal);
  102. 				double fdashM = gstarN + hstarM + cost;
  103. 				m.setFStar(fdashM);
  104. 				m.setParent(minf);
  105. 				if (open.containsKey(m))
  106. 				{
  107. 					if (fdashM < open.get(m).getFStar())
  108. 					{
  109. 						open.put(m, m);
  110. 					}
  111. 				}
  112. 				else if (close.containsKey(m))
  113. 				{
  114. 					if (fdashM < close.get(m).getFStar())
  115. 					{
  116. 						open.put(m, m);
  117. 						close.remove(m);
  118. 					}
  119. 				}
  120. 				else
  121. 				{
  122. 					open.put(m, m);
  123. 				}
  124. 			}
  125. 		}
  126.  
  127. 		Node t = open.get(goal);
  128. 		while (!start.equals(t) && t != null)
  129. 		{
  130. 			map[t.y][t.x] = 7;
  131. 			t = t.getParent();
  132. 		}
  133. 		map[start.y][start.x] = 1;
  134. 		map[goal.y][goal.x] = 2;
  135.  
  136. 		for (int y = 0; y < h; y++)
  137. 		{
  138. 			for (int x = 0; x < w; x++)
  139. 			{
  140. 				System.out.print(map[y][x] + " ");
  141. 			}
  142. 			System.out.println();
  143. 		}
  144.  
  145. 	}
  146.  
  147. 	static double distance(Node n1, Node n2)
  148. 	{
  149. 		double x = (double)(n1.x - n2.x);
  150. 		double y = (double)(n1.y - n2.y);
  151. 		return Math.sqrt(x * x + y * y);
  152. 	}
  153.  
  154. 	static class Node
  155. 	{
  156. 		public final int x;
  157. 		public final int y;
  158. 		private Node parent = null;
  159. 		private double fstar = 0;
  160.  
  161. 		Node(int x, int y)
  162. 		{
  163. 			this.x = x;
  164. 			this.y = y;
  165. 		}
  166.  
  167. 		void setFStar(double fstar)
  168. 		{
  169. 			this.fstar = fstar;
  170. 		}
  171.  
  172. 		double getFStar()
  173. 		{
  174. 			return this.fstar;
  175. 		}
  176.  
  177. 		void setParent(Node parent)
  178. 		{
  179. 			this.parent = parent;
  180. 		}
  181.  
  182. 		Node getParent()
  183. 		{
  184. 			return this.parent;
  185. 		}
  186.  
  187. 		@Override
  188. 		public int hashCode()
  189. 		{
  190. 			return this.x ^ this.y;
  191. 		}
  192.  
  193. 		@Override
  194. 		public boolean equals(Object obj)
  195. 		{
  196. 			if (obj == this) return true;
  197. 			if (obj == null) return false;
  198. 			if (!this.getClass().equals(obj.getClass())) return false;
  199. 			Node node = (Node)obj;
  200. 			return this.x == node.x && this.y == node.y;
  201. 		}
  202. 	}
  203. }
Success #stdin #stdout 0.1s 380736KB
comments (?)
stdin 
8 5
0 0 0 3 3 0 0 0
0 0 0 0 3 0 0 0
0 1 0 0 3 0 2 0
0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0
stdout 
0 0 0 3 3 0 0 0 
0 0 0 0 3 0 0 0 
0 1 7 7 3 0 2 0 
0 0 0 7 3 7 7 0 
0 0 0 7 7 7 0 0
https://ideone.com/CbOXD7
A* - Wikipedia
http://j...content-available-to-author-only...a.org/wiki/A*
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!