fork(1) 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.1s 380736KB
stdin
9 10
0 0 0 0 0 0 0 0 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 0 0 0
0 0 0 0 0 0 0 0 0
3 3 3 3 3 3 3 3 0
0 0 0 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 0 0 0 0 0 0 0 0
stdout
success: 39
0 0 0 0 0 0 0 0 0 
0 0 0 0 2 8 8 0 0 
0 0 0 0 8 7 8 8 0 
0 0 0 0 8 8 7 8 8 
0 0 0 0 0 8 8 7 8 
3 3 3 3 3 3 3 3 7 
8 8 8 8 8 7 7 7 8 
8 8 8 8 7 8 8 8 8 
0 0 0 8 1 8 0 0 0 
0 0 0 8 8 8 0 0 0