API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 29th, 2016
60
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 28.44 KB | None | 0 0
raw download clone embed print report
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.io.FileWriter;
  4. import java.util.*;
  5.  
  6. /**
  7. * Created by Drys on 06.04.2016.
  8. */
  9. public class Run {
  10. int[] fringeVal = new int[6];
  11. Cell arr[][][][];
  12. public class XY {
  13. int x,y;
  14.  
  15. public XY(int x, int y) {
  16. this.x = x;
  17. this.y = y;
  18. }
  19.  
  20. public int getX() {
  21. return x;
  22. }
  23.  
  24. public int getY() {
  25. return y;
  26. }
  27. }
  28. public class Pair implements Comparable{
  29. private int penalty;
  30. private Cell cell;
  31. public Pair(int penalty, Cell cell) {
  32. this.penalty = penalty;
  33. this.cell = cell;
  34. }
  35.  
  36. public int getPenalty() {
  37. return penalty;
  38. }
  39.  
  40. public Cell getCell() {
  41. return cell;
  42. }
  43.  
  44. @Override
  45. public int compareTo(Object o) {
  46. return penalty - ((Pair)o).penalty;
  47. }
  48. }
  49. public class Cell {
  50. private boolean isCheked = false;
  51. private int val;
  52. private int i;
  53. private int j;
  54. private int g;
  55. private int orient;
  56. int shortWay;
  57. Stack<XY> stack = new Stack<>();
  58. private ArrayList<Cell> cells = new ArrayList<>();
  59. private ArrayList<Integer> travelCost = new ArrayList<>();
  60. Cell(int val, int i, int j, int g, int orient) {
  61. this.val = val;
  62. this.i = i;
  63. this.j = j;
  64. this.g = g;
  65. this.orient = orient;
  66. shortWay = 10002;
  67. stack.add(new XY(i ,j));
  68. }
  69. public void createNode() {
  70. if(orient == 0) {
  71. if(g == 0) {
  72. if(j != 0) {
  73. cells.add(arr[i][j - 1][3][0]);
  74. travelCost.add(Math.abs(arr[i][j][3][0].getVal() - fringeVal[3]));
  75. }
  76. if(i != 0) {
  77. cells.add(arr[i - 1][j][4][1]);
  78. travelCost.add(Math.abs(arr[i - 1][j][4][1].getVal() - fringeVal[4]));
  79. }
  80. if(j < arr[0].length - 1) {
  81. cells.add(arr[i][j+1][1][0]);
  82. travelCost.add(Math.abs(arr[i][j+1][1][0].getVal() - fringeVal[1]));
  83. }
  84. if(i < arr.length - 1) {
  85. cells.add(arr[i+1][j][5][3]);
  86. travelCost.add(Math.abs(arr[i+1][j][5][3].getVal() - fringeVal[5]));
  87. }
  88. }
  89. if(g == 1) {
  90. if(j != 0) {
  91. cells.add(arr[i][j - 1][0][0]);
  92. travelCost.add(Math.abs(arr[i][j][0][0].getVal() - fringeVal[0]));
  93. }
  94. if(i != 0) {
  95. cells.add(arr[i - 1][j][4][2]);
  96. travelCost.add(Math.abs(arr[i - 1][j][4][2].getVal() - fringeVal[4]));
  97. }
  98. if(j < arr[0].length - 1) {
  99. cells.add(arr[i][j+1][2][0]);
  100. travelCost.add(Math.abs(arr[i][j+1][2][0].getVal() - fringeVal[2]));
  101. }
  102. if(i < arr.length - 1) {
  103. cells.add(arr[i+1][j][5][0]);
  104. travelCost.add(Math.abs(arr[i+1][j][5][0].getVal() - fringeVal[5]));
  105. }
  106. }
  107. if (g == 2) {
  108. if(j != 0) {
  109. cells.add(arr[i][j - 1][1][0]);
  110. travelCost.add(Math.abs(arr[i][j][1][0].getVal() - fringeVal[1]));
  111. }
  112. if(i != 0) {
  113. cells.add(arr[i - 1][j][4][3]);
  114. travelCost.add(Math.abs(arr[i - 1][j][4][3].getVal() - fringeVal[4]));
  115. }
  116. if(j < arr[0].length - 1) {
  117. cells.add(arr[i][j+1][3][0]);
  118. travelCost.add(Math.abs(arr[i][j+1][3][0].getVal() - fringeVal[3]));
  119. }
  120. if(i < arr.length - 1) {
  121. cells.add(arr[i+1][j][5][1]);
  122. travelCost.add(Math.abs(arr[i+1][j][5][1].getVal() - fringeVal[5]));
  123. }
  124. }
  125. if (g == 3) {
  126. if(j != 0) {
  127. cells.add(arr[i][j - 1][2][0]);
  128. travelCost.add(Math.abs(arr[i][j][2][0].getVal() - fringeVal[2]));
  129. }
  130. if(i != 0) {
  131. cells.add(arr[i - 1][j][4][0]);
  132. travelCost.add(Math.abs(arr[i - 1][j][4][0].getVal() - fringeVal[4]));
  133. }
  134. if(j < arr[0].length - 1) {
  135. cells.add(arr[i][j+1][0][0]);
  136. travelCost.add(Math.abs(arr[i][j+1][0][0].getVal() - fringeVal[0]));
  137. }
  138. if(i < arr.length - 1) {
  139. cells.add(arr[i+1][j][5][0]);
  140. travelCost.add(Math.abs(arr[i+1][j][5][0].getVal() - fringeVal[5]));
  141. }
  142. }
  143. if (g == 4) {
  144. if(j != 0) {
  145. cells.add(arr[i][j - 1][2][1]);
  146. travelCost.add(Math.abs(arr[i][j][2][1].getVal() - fringeVal[2]));
  147. }
  148. if(i != 0) {
  149. cells.add(arr[i - 1][j][1][2]);
  150. travelCost.add(Math.abs(arr[i - 1][j][1][2].getVal() - fringeVal[1]));
  151. }
  152. if(j < arr[0].length - 1) {
  153. cells.add(arr[i][j+1][0][3]);
  154. travelCost.add(Math.abs(arr[i][j+1][0][3].getVal() - fringeVal[0]));
  155. }
  156. if(i < arr.length - 1) {
  157. cells.add(arr[i+1][j][3][0]);
  158. travelCost.add(Math.abs(arr[i+1][j][3][0].getVal() - fringeVal[3]));
  159. }
  160. }
  161. if (g == 5) {
  162. if(j != 0) {
  163. cells.add(arr[i][j - 1][2][3]);
  164. travelCost.add(Math.abs(arr[i][j][2][3].getVal() - fringeVal[2]));
  165. }
  166. if(i != 0) {
  167. cells.add(arr[i - 1][j][3][0]);
  168. travelCost.add(Math.abs(arr[i - 1][j][3][0].getVal() - fringeVal[3]));
  169. }
  170. if(j < arr[0].length - 1) {
  171. cells.add(arr[i][j+1][0][1]);
  172. travelCost.add(Math.abs(arr[i][j+1][0][1].getVal() - fringeVal[0]));
  173. }
  174. if(i < arr.length - 1) {
  175. cells.add(arr[i+1][j][1][2]);
  176. travelCost.add(Math.abs(arr[i+1][j][1][2].getVal() - fringeVal[1]));
  177. }
  178. }
  179. } else {
  180. if (orient == 1) {
  181. if(g == 0) {
  182. if(j != 0) {
  183. cells.add(arr[i][j - 1][5][0]);
  184. travelCost.add(Math.abs(arr[i][j][5][0].getVal() - fringeVal[5]));
  185. }
  186. if(i != 0) {
  187. cells.add(arr[i - 1][j][3][1]);
  188. travelCost.add(Math.abs(arr[i - 1][j][3][1].getVal() - fringeVal[3]));
  189. }
  190. if(j < arr[0].length - 1) {
  191. cells.add(arr[i][j+1][4][2]);
  192. travelCost.add(Math.abs(arr[i][j+1][4][2].getVal() - fringeVal[4]));
  193. }
  194. if(i < arr.length - 1) {
  195. cells.add(arr[i+1][j][1][1]);
  196. travelCost.add(Math.abs(arr[i+1][j][1][1].getVal() - fringeVal[1]));
  197. }
  198. }
  199. if(g == 1) {
  200. if(j != 0) {
  201. cells.add(arr[i][j - 1][5][3]);
  202. travelCost.add(Math.abs(arr[i][j][5][3].getVal() - fringeVal[5]));
  203. }
  204. if(i != 0) {
  205. cells.add(arr[i - 1][j][0][1]);
  206. travelCost.add(Math.abs(arr[i - 1][j][0][1].getVal() - fringeVal[0]));
  207. }
  208. if(j < arr[0].length - 1) {
  209. cells.add(arr[i][j+1][4][3]);
  210. travelCost.add(Math.abs(arr[i][j+1][4][3].getVal() - fringeVal[4]));
  211. }
  212. if(i < arr.length - 1) {
  213. cells.add(arr[i+1][j][2][1]);
  214. travelCost.add(Math.abs(arr[i+1][j][2][1].getVal() - fringeVal[2]));
  215. }
  216. }
  217. if (g == 2) {
  218. if(j != 0) {
  219. cells.add(arr[i][j - 1][5][2]);
  220. travelCost.add(Math.abs(arr[i][j][5][2].getVal() - fringeVal[1]));
  221. }
  222. if(i != 0) {
  223. cells.add(arr[i - 1][j][1][1]);
  224. travelCost.add(Math.abs(arr[i - 1][j][1][1].getVal() - fringeVal[1]));
  225. }
  226. if(j < arr[0].length - 1) {
  227. cells.add(arr[i][j+1][4][0]);
  228. travelCost.add(Math.abs(arr[i][j+1][4][0].getVal() - fringeVal[4]));
  229. }
  230. if(i < arr.length - 1) {
  231. cells.add(arr[i+1][j][3][1]);
  232. travelCost.add(Math.abs(arr[i+1][j][3][1].getVal() - fringeVal[3]));
  233. }
  234. }
  235. if (g == 3) {
  236. if(j != 0) {
  237. cells.add(arr[i][j - 1][5][1]);
  238. travelCost.add(Math.abs(arr[i][j][5][1].getVal() - fringeVal[5]));
  239. }
  240. if(i != 0) {
  241. cells.add(arr[i - 1][j][2][1]);
  242. travelCost.add(Math.abs(arr[i - 1][j][2][1].getVal() - fringeVal[2]));
  243. }
  244. if(j < arr[0].length - 1) {
  245. cells.add(arr[i][j+1][4][1]);
  246. travelCost.add(Math.abs(arr[i][j+1][4][1].getVal() - fringeVal[1]));
  247. }
  248. if(i < arr.length - 1) {
  249. cells.add(arr[i+1][j][0][1]);
  250. travelCost.add(Math.abs(arr[i+1][j][0][1].getVal() - fringeVal[0]));
  251. }
  252. }
  253. if (g == 4) {
  254. if(j != 0) {
  255. cells.add(arr[i][j - 1][3][1]);
  256. travelCost.add(Math.abs(arr[i][j][3][1].getVal() - fringeVal[3]));
  257. }
  258. if(i != 0) {
  259. cells.add(arr[i - 1][j][2][2]);
  260. travelCost.add(Math.abs(arr[i - 1][j][2][2].getVal() - fringeVal[2]));
  261. }
  262. if(j < arr[0].length - 1) {
  263. cells.add(arr[i][j+1][1][3]);
  264. travelCost.add(Math.abs(arr[i][j+1][1][3].getVal() - fringeVal[1]));
  265. }
  266. if(i < arr.length - 1) {
  267. cells.add(arr[i+1][j][0][0]);
  268. travelCost.add(Math.abs(arr[i+1][j][0][0].getVal() - fringeVal[0]));
  269. }
  270. }
  271. if (g == 5) {
  272. if(j != 0) {
  273. cells.add(arr[i][j - 1][1][3]);
  274. travelCost.add(Math.abs(arr[i][j][1][3].getVal() - fringeVal[1]));
  275. }
  276. if(i != 0) {
  277. cells.add(arr[i - 1][j][2][0]);
  278. travelCost.add(Math.abs(arr[i - 1][j][2][0].getVal() - fringeVal[2]));
  279. }
  280. if(j < arr[0].length - 1) {
  281. cells.add(arr[i][j+1][3][1]);
  282. travelCost.add(Math.abs(arr[i][j+1][3][1].getVal() - fringeVal[3]));
  283. }
  284. if(i < arr.length - 1) {
  285. cells.add(arr[i+1][j][0][2]);
  286. travelCost.add(Math.abs(arr[i+1][j][0][2].getVal() - fringeVal[0]));
  287. }
  288. }
  289. } else {
  290. if (orient == 2) {
  291. if(g == 0) {
  292. if(j != 0) {
  293. cells.add(arr[i][j - 1][1][2]);
  294. travelCost.add(Math.abs(arr[i][j][1][2].getVal() - fringeVal[1]));
  295. }
  296. if(i != 0) {
  297. cells.add(arr[i - 1][j][5][1]);
  298. travelCost.add(Math.abs(arr[i - 1][j][5][1].getVal() - fringeVal[5]));
  299. }
  300. if(j < arr[0].length - 1) {
  301. cells.add(arr[i][j+1][3][2]);
  302. travelCost.add(Math.abs(arr[i][j+1][3][2].getVal() - fringeVal[3]));
  303. }
  304. if(i < arr.length - 1) {
  305. cells.add(arr[i+1][j][4][3]);
  306. travelCost.add(Math.abs(arr[i+1][j][4][3].getVal() - fringeVal[4]));
  307. }
  308. }
  309. if(g == 1) {
  310. if(j != 0) {
  311. cells.add(arr[i][j - 1][2][2]);
  312. travelCost.add(Math.abs(arr[i][j][2][2].getVal() - fringeVal[2]));
  313. }
  314. if(i != 0) {
  315. cells.add(arr[i - 1][j][5][0]);
  316. travelCost.add(Math.abs(arr[i - 1][j][5][0].getVal() - fringeVal[5]));
  317. }
  318. if(j < arr[0].length - 1) {
  319. cells.add(arr[i][j+1][0][2]);
  320. travelCost.add(Math.abs(arr[i][j+1][0][2].getVal() - fringeVal[0]));
  321. }
  322. if(i < arr.length - 1) {
  323. cells.add(arr[i+1][j][4][0]);
  324. travelCost.add(Math.abs(arr[i+1][j][4][0].getVal() - fringeVal[4]));
  325. }
  326. }
  327. if (g == 2) {
  328. if(j != 0) {
  329. cells.add(arr[i][j - 1][3][2]);
  330. travelCost.add(Math.abs(arr[i][j][3][2].getVal() - fringeVal[3]));
  331. }
  332. if(i != 0) {
  333. cells.add(arr[i - 1][j][5][3]);
  334. travelCost.add(Math.abs(arr[i - 1][j][5][3].getVal() - fringeVal[5]));
  335. }
  336. if(j < arr[0].length - 1) {
  337. cells.add(arr[i][j+1][1][2]);
  338. travelCost.add(Math.abs(arr[i][j+1][1][2].getVal() - fringeVal[1]));
  339. }
  340. if(i < arr.length - 1) {
  341. cells.add(arr[i+1][j][4][1]);
  342. travelCost.add(Math.abs(arr[i+1][j][4][1].getVal() - fringeVal[4]));
  343. }
  344. }
  345. if (g == 3) {
  346. if(j != 0) {
  347. cells.add(arr[i][j - 1][0][2]);
  348. travelCost.add(Math.abs(arr[i][j][0][2].getVal() - fringeVal[0]));
  349. }
  350. if(i != 0) {
  351. cells.add(arr[i - 1][j][5][2]);
  352. travelCost.add(Math.abs(arr[i - 1][j][5][2].getVal() - fringeVal[5]));
  353. }
  354. if(j < arr[0].length - 1) {
  355. cells.add(arr[i][j+1][2][2]);
  356. travelCost.add(Math.abs(arr[i][j+1][2][2].getVal() - fringeVal[2]));
  357. }
  358. if(i < arr.length - 1) {
  359. cells.add(arr[i+1][j][4][2]);
  360. travelCost.add(Math.abs(arr[i+1][j][4][2].getVal() - fringeVal[4]));
  361. }
  362. }
  363. if (g == 4) {
  364. if(j != 0) {
  365. cells.add(arr[i][j - 1][0][1]);
  366. travelCost.add(Math.abs(arr[i][j][0][1].getVal() - fringeVal[0]));
  367. }
  368. if(i != 0) {
  369. cells.add(arr[i - 1][j][3][2]);
  370. travelCost.add(Math.abs(arr[i - 1][j][3][2].getVal() - fringeVal[3]));
  371. }
  372. if(j < arr[0].length - 1) {
  373. cells.add(arr[i][j+1][2][3]);
  374. travelCost.add(Math.abs(arr[i][j+1][2][3].getVal() - fringeVal[2]));
  375. }
  376. if(i < arr.length - 1) {
  377. cells.add(arr[i+1][j][1][0]);
  378. travelCost.add(Math.abs(arr[i+1][j][1][0].getVal() - fringeVal[1]));
  379. }
  380. }
  381. if (g == 5) {
  382. if(j != 0) {
  383. cells.add(arr[i][j - 1][0][3]);
  384. travelCost.add(Math.abs(arr[i][j][0][3].getVal() - fringeVal[0]));
  385. }
  386. if(i != 0) {
  387. cells.add(arr[i - 1][j][1][0]);
  388. travelCost.add(Math.abs(arr[i - 1][j][1][0].getVal() - fringeVal[1]));
  389. }
  390. if(j < arr[0].length - 1) {
  391. cells.add(arr[i][j+1][2][1]);
  392. travelCost.add(Math.abs(arr[i][j+1][2][1].getVal() - fringeVal[2]));
  393. }
  394. if(i < arr.length - 1) {
  395. cells.add(arr[i+1][j][3][2]);
  396. travelCost.add(Math.abs(arr[i+1][j][3][2].getVal() - fringeVal[3]));
  397. }
  398. }
  399. } else {
  400. if(g == 0) {
  401. if(j != 0) {
  402. cells.add(arr[i][j - 1][4][0]);
  403. travelCost.add(Math.abs(arr[i][j][4][0].getVal() - fringeVal[4]));
  404. }
  405. if(i != 0) {
  406. cells.add(arr[i - 1][j][1][3]);
  407. travelCost.add(Math.abs(arr[i - 1][j][1][3].getVal() - fringeVal[1]));
  408. }
  409. if(j < arr[0].length - 1) {
  410. cells.add(arr[i][j+1][5][2]);
  411. travelCost.add(Math.abs(arr[i][j+1][5][2].getVal() - fringeVal[5]));
  412. }
  413. if(i < arr.length - 1) {
  414. cells.add(arr[i+1][j][3][3]);
  415. travelCost.add(Math.abs(arr[i+1][j][3][3].getVal() - fringeVal[3]));
  416. }
  417. }
  418. if(g == 1) {
  419. if(j != 0) {
  420. cells.add(arr[i][j - 1][4][1]);
  421. travelCost.add(Math.abs(arr[i][j][4][1].getVal() - fringeVal[4]));
  422. }
  423. if(i != 0) {
  424. cells.add(arr[i - 1][j][2][3]);
  425. travelCost.add(Math.abs(arr[i - 1][j][2][3].getVal() - fringeVal[2]));
  426. }
  427. if(j < arr[0].length - 1) {
  428. cells.add(arr[i][j+1][5][1]);
  429. travelCost.add(Math.abs(arr[i][j+1][5][1].getVal() - fringeVal[5]));
  430. }
  431. if(i < arr.length - 1) {
  432. cells.add(arr[i+1][j][0][3]);
  433. travelCost.add(Math.abs(arr[i+1][j][0][3].getVal() - fringeVal[0]));
  434. }
  435. }
  436. if (g == 2) {
  437. if(j != 0) {
  438. cells.add(arr[i][j - 1][4][2]);
  439. travelCost.add(Math.abs(arr[i][j][4][2].getVal() - fringeVal[4]));
  440. }
  441. if(i != 0) {
  442. cells.add(arr[i - 1][j][3][3]);
  443. travelCost.add(Math.abs(arr[i - 1][j][3][3].getVal() - fringeVal[3]));
  444. }
  445. if(j < arr[0].length - 1) {
  446. cells.add(arr[i][j+1][5][0]);
  447. travelCost.add(Math.abs(arr[i][j+1][5][0].getVal() - fringeVal[5]));
  448. }
  449. if(i < arr.length - 1) {
  450. cells.add(arr[i+1][j][1][3]);
  451. travelCost.add(Math.abs(arr[i+1][j][1][3].getVal() - fringeVal[1]));
  452. }
  453. }
  454. if (g == 3) {
  455. if(j != 0) {
  456. cells.add(arr[i][j - 1][4][3]);
  457. travelCost.add(Math.abs(arr[i][j][4][3].getVal() - fringeVal[4]));
  458. }
  459. if(i != 0) {
  460. cells.add(arr[i - 1][j][0][3]);
  461. travelCost.add(Math.abs(arr[i - 1][j][0][3].getVal() - fringeVal[0]));
  462. }
  463. if(j < arr[0].length - 1) {
  464. cells.add(arr[i][j+1][5][3]);
  465. travelCost.add(Math.abs(arr[i][j+1][5][3].getVal() - fringeVal[5]));
  466. }
  467. if(i < arr.length - 1) {
  468. cells.add(arr[i+1][j][2][3]);
  469. travelCost.add(Math.abs(arr[i+1][j][2][3].getVal() - fringeVal[2]));
  470. }
  471. }
  472. if (g == 4) {
  473. if(j != 0) {
  474. cells.add(arr[i][j - 1][1][1]);
  475. travelCost.add(Math.abs(arr[i][j][1][1].getVal() - fringeVal[1]));
  476. }
  477. if(i != 0) {
  478. cells.add(arr[i - 1][j][0][2]);
  479. travelCost.add(Math.abs(arr[i - 1][j][0][2].getVal() - fringeVal[0]));
  480. }
  481. if(j < arr[0].length - 1) {
  482. cells.add(arr[i][j+1][3][3]);
  483. travelCost.add(Math.abs(arr[i][j+1][3][3].getVal() - fringeVal[3]));
  484. }
  485. if(i < arr.length - 1) {
  486. cells.add(arr[i+1][j][2][0]);
  487. travelCost.add(Math.abs(arr[i+1][j][2][0].getVal() - fringeVal[2]));
  488. }
  489. }
  490. if (g == 5) {
  491. if(j != 0) {
  492. cells.add(arr[i][j - 1][3][3]);
  493. travelCost.add(Math.abs(arr[i][j][3][3].getVal() - fringeVal[3]));
  494. }
  495. if(i != 0) {
  496. cells.add(arr[i - 1][j][0][0]);
  497. travelCost.add(Math.abs(arr[i - 1][j][0][0].getVal() - fringeVal[0]));
  498. }
  499. if(j < arr[0].length - 1) {
  500. cells.add(arr[i][j+1][1][1]);
  501. travelCost.add(Math.abs(arr[i][j+1][1][1].getVal() - fringeVal[1]));
  502. }
  503. if(i < arr.length - 1) {
  504. cells.add(arr[i+1][j][2][2]);
  505. travelCost.add(Math.abs(arr[i+1][j][2][2].getVal() - fringeVal[2]));
  506. }
  507. }
  508. }
  509. }
  510. }
  511. }
  512.  
  513. public boolean isCheked() {
  514. return isCheked;
  515. }
  516.  
  517. public void setCheked(boolean cheked) {
  518. isCheked = cheked;
  519. }
  520.  
  521.  
  522.  
  523. public int getVal() {
  524. return val;
  525. }
  526. }
  527.  
  528. public static void main(String[] args) throws Exception {
  529. Run obj = new Run();
  530. obj.run(args);
  531. }
  532. public void run(String[] args) throws Exception {
  533. Scanner sc = new Scanner(new File("input.txt"));
  534. int n = sc.nextInt();
  535. int m = sc.nextInt();
  536. arr = new Cell[n][m][6][4];
  537. for (int j = 0; j < n; j++) {
  538. for (int i = 0; i < m; i++) {
  539. int value = sc.nextInt();
  540. for (int g = 0; g < 6; g++) {
  541. for (int orient = 0; orient < 4; orient++) {
  542. arr[i][j][g][orient] = new Cell(value, i, j, g,orient);
  543. }
  544. }
  545. }
  546. }
  547. for (int i = 0 ; i < 6; i++) {
  548. fringeVal[i] = sc.nextInt();
  549. }
  550. for (int i = 0; i < n; i++) {
  551. for (int j = 0; j < m; j++) {
  552. for (int g = 0; g < 6; g++) {
  553. for (int orient = 0; orient < 4; orient++) {
  554. arr[i][j][g][orient].createNode();
  555. }
  556. }
  557. }
  558. }
  559. int q = sc.nextInt() - 1;
  560. int w = sc.nextInt() - 1;
  561. arr[q][w][1][0].shortWay = 0;
  562. dejkstra(new PriorityQueue<>(Arrays.asList(new Pair(0,arr[q][w][1][0]))));
  563. int c = 0,d = 0;
  564. int a = sc.nextInt() - 1;
  565. int b = sc.nextInt() - 1;
  566. for(int i = 0; i < 6; i++){
  567. for(int j = 0; j < 4; j++){
  568. if(arr[a][b][i][j].shortWay < arr[a][b][c][d].shortWay) {
  569. c = i;
  570. d = j;
  571. }
  572. }
  573. }
  574. FileWriter fileWriter = new FileWriter(new File("output.txt"));
  575. fileWriter.write(arr[a][b][c][d].stack.size() + "\n");
  576. int h = arr[a][b][c][d].stack.size();
  577. for (int i = 0; i < h; i++) {
  578. XY x = arr[a][b][c][d].stack.pop();
  579. fileWriter.write((x.getX() + 1) + " " + (x.getY()+ 1) + "\n" );
  580. }
  581. fileWriter.close();
  582. }
  583. public void dejkstra(PriorityQueue<Pair> steps) {
  584. Cell cell = steps.remove().getCell();
  585. for(int i = 0; i < cell.cells.size(); i++) {
  586. if(!cell.cells.get(i).isCheked) {
  587. int path = cell.shortWay + cell.travelCost.get(i);
  588. if (cell.cells.get(i).shortWay >= path) {
  589. cell.cells.get(i).shortWay = path;
  590. cell.cells.get(i).stack = new Stack<>();
  591. cell.cells.get(i).stack.add(new XY( cell.cells.get(i).i, cell.cells.get(i).j));
  592. cell.cells.get(i).stack.addAll(cell.stack);
  593. Pair pair = new Pair(path,cell.cells.get(i));
  594. if(!steps.contains(pair)) {
  595. steps.add(pair);
  596. }
  597. }
  598. }
  599. }
  600. cell.setCheked(true);
  601. if(!steps.isEmpty())
  602. dejkstra(steps);
  603. }
  604. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!