fork download 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 	public static void main (String[] args) throws java.lang.Exception
  8. 	{
  9. 		Ideone obj = new Ideone();
  10.  
  11. 		if (!obj.loadMap())
  12. 		{
  13. 			System.out.println("wrong inputs");
  14. 			return;
  15. 		}
  16.  
  17. 		int c = obj.astarsearch();
  18.  
  19. 		if (c < 0)
  20. 		{
  21. 			System.out.println("failure");
  22. 		}
  23. 		else
  24. 		{
  25. 			System.out.println("success: " + c);
  26. 		}
  27.  
  28. 		obj.printMap();
  29. 	}
  30.  
  31. 	int[][] map = null;
  32. 	int width = 0;
  33. 	int height = 0;
  34. 	Node start = null;
  35. 	Node goal = null;
  36.  
  37. 	boolean loadMap()
  38. 	{
  39. 		Scanner sc = new Scanner(System.in);
  40. 		if (!sc.hasNextInt())
  41. 		{
  42. 			return false;
  43. 		}
  44. 		width = sc.nextInt();
  45. 		if (!sc.hasNextInt())
  46. 		{
  47. 			return false;
  48. 		}
  49. 		height = sc.nextInt();
  50. 		map = new int[height][width];
  51. 		for (int y = 0; y < height; y++)
  52. 		{
  53. 			for (int x = 0; x < width; x++)
  54. 			{
  55. 				if (!sc.hasNextInt())
  56. 				{
  57. 					return false;
  58. 				}
  59. 				map[y][x] = sc.nextInt();
  60. 				switch (map[y][x])
  61. 				{
  62. 					case 0:
  63. 					{
  64. 						break;
  65. 					}
  66. 					case 1:
  67. 					{
  68. 						start = new Node(x, y);
  69. 						break;
  70. 					}
  71. 					case 2:
  72. 					{
  73. 						goal = new Node(x, y);
  74. 						break;
  75. 					}
  76. 					case 3:
  77. 					{
  78. 						break;
  79. 					}
  80. 					default:
  81. 					{
  82. 						return false;
  83. 					}
  84. 				}
  85. 			}
  86. 		}
  87. 		return start != null && goal != null;
  88. 	}
  89.  
  90. 	class Node
  91. 	{
  92. 		public int x;
  93. 		public int y;
  94. 		Node(int x, int y)
  95. 		{
  96. 			this.x = x;
  97. 			this.y = y;
  98. 		}
  99. 	}
  100.  
  101. 	void printMap()
  102. 	{
  103. 		if (map == null)
  104. 		{
  105. 			return;
  106. 		}
  107.  
  108. 		for (int y = 0; y < height; y++)
  109. 		{
  110. 			for (int x = 0; x < width; x++)
  111. 			{
  112. 				System.out.print(map[y][x] + " ");
  113. 			}
  114. 			System.out.println();
  115. 		}
  116. 	}
  117.  
  118. 	int parentValue(int x, int y)
  119. 	{
  120. 		return y * width + x;
  121. 	}
  122.  
  123. 	int parentX(int pv)
  124. 	{
  125. 		return pv % width;
  126. 	}
  127.  
  128. 	int parentY(int pv)
  129. 	{
  130. 		return pv / width;
  131. 	}
  132.  
  133. 	double distance(int x1, int y1, int x2, int y2)
  134. 	{
  135. 		int x = x1 - x2;
  136. 		int y = y1 - y2;
  137. 		int s = x * x + y * y;
  138. 		return Math.sqrt((double)s);
  139. 	}
  140.  
  141. 	double cost(int fromX, int fromY, int toX, int toY)
  142. 	{
  143. 		return 0;
  144. 	}
  145.  
  146. 	int astarsearch()
  147. 	{
  148. 		if (start == null || goal == null)
  149. 		{
  150. 			return -1;
  151. 		}
  152.  
  153. 		boolean[][] open = new boolean[height][width];
  154. 		boolean[][] close = new boolean[height][width];
  155. 		double[][] hstar = new double[height][width];
  156. 		double[][] fstar = new double[height][width];
  157. 		int[][] parent = new int[height][width];
  158.  
  159. 		for (int y = 0; y < height; y++)
  160. 		{
  161. 			for (int x = 0; x < width; x++)
  162. 			{
  163. 				hstar[y][x] = distance(x, y, goal.x, goal.y);
  164. 			}
  165. 		}
  166. 		open[start.y][start.x] = true;
  167. 		fstar[start.y][start.x] = hstar[start.y][start.x];
  168.  
  169. 		Node n;
  170. 		for (;;)
  171. 		{
  172. 			n = null;
  173. 			for (int y = 0; y < height; y++)
  174. 			{
  175. 				for (int x = 0; x < width; x++)
  176. 				{
  177. 					if (!open[y][x])
  178. 					{
  179. 						continue;
  180. 					}
  181. 					if (n == null)
  182. 					{
  183. 						n = new Node(x, y);
  184. 					}
  185. 					else if (fstar[y][x] < fstar[n.y][n.x])
  186. 					{
  187. 						n.y = y;
  188. 						n.x = x;
  189. 					}
  190. 				}
  191. 			}
  192.  
  193. 			if (n == null)
  194. 			{
  195. 				return -1;
  196. 			}
  197.  
  198. 			if (n.x == goal.x && n.y == goal.y)
  199. 			{
  200. 				break;
  201. 			}
  202.  
  203. 			open[n.y][n.x] = false;
  204. 			close[n.y][n.x] = true;
  205.  
  206. 			double gstar = fstar[n.y][n.x] - hstar[n.y][n.x];
  207.  
  208. 			for (int dy = -1; dy <= 1; dy++)
  209. 			{
  210. 				for (int dx = -1; dx <= 1; dx++)
  211. 				{
  212. 					if (dy == 0 && dx == 0)
  213. 					{
  214. 						continue;
  215. 					}
  216. 					int x = n.x + dx;
  217. 					int y = n.y + dy;
  218. 					if (x < 0 || x >= width || y < 0 || y >= height)
  219. 					{
  220. 						continue;
  221. 					}
  222. 					if (map[y][x] == 3)
  223. 					{
  224. 						continue;
  225. 					}
  226. 					double fdash = gstar
  227. 								+ hstar[y][x]
  228. 								+ cost(n.x, n.y, x, y);
  229. 					if (open[y][x] || close[y][x])
  230. 					{
  231. 						if (fdash >= fstar[y][x])
  232. 						{
  233. 							continue;
  234. 						}
  235. 					}
  236. 					open[y][x] = true;
  237. 					close[y][x] = false;
  238. 					fstar[y][x] = fdash;
  239. 					parent[y][x] = parentValue(n.x, n.y);
  240. 					if (map[y][x] == 0)
  241. 					{
  242. 						map[y][x] = 8;
  243. 					}
  244. 				}
  245. 			}
  246. 		}
  247.  
  248. 		while (n.x != start.x || n.y != start.y)
  249. 		{
  250. 			if (map[n.y][n.x] == 8)
  251. 			{
  252. 				map[n.y][n.x] = 7;
  253. 			}
  254. 			int pv = parent[n.y][n.x];
  255. 			n.x = parentX(pv);
  256. 			n.y = parentY(pv);
  257. 		}
  258.  
  259. 		int c = 0;
  260. 		for (int y = 0; y < height; y++)
  261. 		{
  262. 			for (int x = 0; x < width; x++)
  263. 			{
  264. 				if (map[y][x] >= 7)
  265. 				{
  266. 					c++;
  267. 				}
  268. 			}
  269. 		}
  270. 		return c;
  271. 	}
  272. }
Success #stdin #stdout 0.11s 380672KB
comments (?)
stdin 
9 5
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
stdout 
success: 22
0 0 0 0 0 0 0 0 0 
8 8 8 8 8 8 8 8 0 
8 1 7 7 7 7 7 2 0 
8 8 8 8 8 8 8 8 0 
0 0 0 0 0 0 0 0 0
https://ideone.com/JNRRcg
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!