fork download
copy 
  1. // A C++ Program to implement A* Search Algorithm
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ROW 17
  6. #define COL 15
  7.  
  8. // Creating a shortcut for int, int pair type
  9. typedef pair<int, int> Pair;
  10.  
  11. // Creating a shortcut for pair<int, pair<int, int>> type
  12. typedef pair<double, pair<int, int> > pPair;
  13.  
  14. namespace std {
  15.     template <>
  16.     struct hash<pPair> {
  17.         std::size_t operator()(pPair const& instance) const {
  18.             return std::hash<double>()(instance.first) ^ std::hash<int>()(instance.second.first) ^ std::hash<int>()(instance.second.second);
  19.         }
  20.     };
  21. }
  22.  
  23. // A structure to hold the necessary parameters
  24. struct cell {
  25. 	// Row and Column index of its parent
  26. 	// Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
  27. 	int parent_i, parent_j;
  28. 	// f = g + h
  29. 	double f, g, h;
  30. };
  31.  
  32. // A Utility Function to check whether given cell (row, col)
  33. // is a valid cell or not.
  34. bool isValid(int row, int col)
  35. {
  36. 	// Returns true if row number and column number
  37. 	// is in range
  38. 	return (row >= 0) && (row < ROW) && (col >= 0)
  39. 		&& (col < COL);
  40. }
  41.  
  42. // A Utility Function to check whether the given cell is
  43. // blocked or not
  44. bool isUnBlocked(int grid[][COL], int row, int col)
  45. {
  46. 	// Returns true if the cell is not blocked else false
  47. 	if (grid[row][col] != 0)
  48. 		return (true);
  49. 	else
  50. 		return (false);
  51. }
  52.  
  53. // A Utility Function to check whether destination cell has
  54. // been reached or not
  55. bool isDestination(int row, int col, Pair dest)
  56. {
  57. 	if (row == dest.first && col == dest.second)
  58. 		return (true);
  59. 	else
  60. 		return (false);
  61. }
  62.  
  63. // A Utility Function to calculate the 'h' heuristics.
  64. double calculateHValue(int row, int col, Pair dest)
  65. {
  66. 	// Return using the distance formula
  67. 	return ((double)sqrt(
  68. 		(row - dest.first) * (row - dest.first)
  69. 		+ (col - dest.second) * (col - dest.second)));
  70. }
  71.  
  72. // A Utility Function to trace the path from the source
  73. // to destination
  74. void tracePath(cell cellDetails[][COL], Pair dest)
  75. {
  76. 	printf("\nThe Path is ");
  77. 	int row = dest.first;
  78. 	int col = dest.second;
  79.  
  80. 	stack<Pair> Path;
  81.  
  82. 	while (!(cellDetails[row][col].parent_i == row
  83. 			&& cellDetails[row][col].parent_j == col)) {
  84. 		Path.push(make_pair(row, col));
  85. 		int temp_row = cellDetails[row][col].parent_i;
  86. 		int temp_col = cellDetails[row][col].parent_j;
  87. 		row = temp_row;
  88. 		col = temp_col;
  89. 	}
  90.  
  91. 	Path.push(make_pair(row, col));
  92. 	while (!Path.empty()) {
  93. 		pair<int, int> p = Path.top();
  94. 		Path.pop();
  95. 		printf("-> (%d,%d) ", p.first, p.second);
  96. 	}
  97.  
  98. 	return;
  99. }
  100.  
  101. // A Function to find the shortest path between
  102. // a given source cell to a destination cell according
  103. // to A* Search Algorithm
  104. void aStarSearch(int grid[][COL], Pair src, Pair dest)
  105. {
  106. 	// If the source is out of range
  107. 	if (isValid(src.first, src.second) == false) {
  108. 		printf("Source is invalid\n");
  109. 		return;
  110. 	}
  111.  
  112. 	// If the destination is out of range
  113. 	if (isValid(dest.first, dest.second) == false) {
  114. 		printf("Destination is invalid\n");
  115. 		return;
  116. 	}
  117.  
  118. 	// Either the source or the destination is blocked
  119. 	if (isUnBlocked(grid, src.first, src.second) == false
  120. 		|| isUnBlocked(grid, dest.first, dest.second)
  121. 			== false) {
  122. 		printf("Source or the destination is blocked\n");
  123. 		return;
  124. 	}
  125.  
  126. 	// If the destination cell is the same as source cell
  127. 	if (isDestination(src.first, src.second, dest)
  128. 		== true) {
  129. 		printf("We are already at the destination\n");
  130. 		return;
  131. 	}
  132.  
  133. 	// Create a closed list and initialise it to false which
  134. 	// means that no cell has been included yet This closed
  135. 	// list is implemented as a boolean 2D array
  136. 	bool closedList[ROW][COL];
  137. 	memset(closedList, false, sizeof(closedList));
  138.  
  139. 	// Declare a 2D array of structure to hold the details
  140. 	// of that cell
  141. 	cell cellDetails[ROW][COL];
  142.  
  143. 	int i, j;
  144.  
  145. 	for (i = 0; i < ROW; i++) {
  146. 		for (j = 0; j < COL; j++) {
  147. 			cellDetails[i][j].f = FLT_MAX;
  148. 			cellDetails[i][j].g = FLT_MAX;
  149. 			cellDetails[i][j].h = FLT_MAX;
  150. 			cellDetails[i][j].parent_i = -1;
  151. 			cellDetails[i][j].parent_j = -1;
  152. 		}
  153. 	}
  154.  
  155. 	// Initialising the parameters of the starting node
  156. 	i = src.first, j = src.second;
  157. 	cellDetails[i][j].f = 0.0;
  158. 	cellDetails[i][j].g = 0.0;
  159. 	cellDetails[i][j].h = 0.0;
  160. 	cellDetails[i][j].parent_i = i;
  161. 	cellDetails[i][j].parent_j = j;
  162.  
  163. 	/*
  164. 	Create an open list having information as-
  165. 	<f, <i, j>>
  166. 	where f = g + h,
  167. 	and i, j are the row and column index of that cell
  168. 	Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
  169. 	This open list is implemented as a set of pair of
  170. 	pair.*/
  171. 	unordered_set<pPair> openList;
  172.  
  173. 	// Put the starting cell on the open list and set its
  174. 	// 'f' as 0
  175. 	openList.insert(make_pair(0.0, make_pair(i, j)));
  176.  
  177. 	// We set this boolean value as false as initially
  178. 	// the destination is not reached.
  179. 	bool foundDest = false;
  180.  
  181. 	while (!openList.empty()) {
  182. 		pPair p = *openList.begin();
  183.  
  184. 		// Remove this vertex from the open list
  185. 		openList.erase(openList.begin());
  186.  
  187. 		// Add this vertex to the closed list
  188. 		i = p.second.first;
  189. 		j = p.second.second;
  190. 		closedList[i][j] = true;
  191.  
  192. 		/*
  193. 		Generating all the 8 successor of this cell
  194.  
  195. 			N.W N N.E
  196. 			\ | /
  197. 				\ | /
  198. 			W----Cell----E
  199. 				/ | \
  200. 				/ | \
  201. 			S.W S S.E
  202.  
  203. 		Cell-->Popped Cell (i, j)
  204. 		N --> North	 (i-1, j)
  205. 		S --> South	 (i+1, j)
  206. 		E --> East	 (i, j+1)
  207. 		W --> West		 (i, j-1)
  208. 		N.E--> North-East (i-1, j+1)
  209. 		N.W--> North-West (i-1, j-1)
  210. 		S.E--> South-East (i+1, j+1)
  211. 		S.W--> South-West (i+1, j-1)*/
  212.  
  213. 		// To store the 'g', 'h' and 'f' of the 8 successors
  214. 		double gNew, hNew, fNew;
  215.  
  216. 		//----------- 1st Successor (North) ------------
  217.  
  218. 		// Only process this cell if this is a valid one
  219. 		if (isValid(i - 1, j) == true) {
  220. 			// If the destination cell is the same as the
  221. 			// current successor
  222. 			if (isDestination(i - 1, j, dest) == true) {
  223. 				// Set the Parent of the destination cell
  224. 				cellDetails[i - 1][j].parent_i = i;
  225. 				cellDetails[i - 1][j].parent_j = j;
  226. 				printf("The destination cell is found\n");
  227. 				tracePath(cellDetails, dest);
  228. 				foundDest = true;
  229. 				return;
  230. 			}
  231. 			// If the successor is already on the closed
  232. 			// list or if it is blocked, then ignore it.
  233. 			// Else do the following
  234. 			else if (closedList[i - 1][j] == false
  235. 					&& isUnBlocked(grid, i - 1, j)
  236. 							== true) {
  237. 				gNew = cellDetails[i][j].g + 1.0;
  238. 				hNew = calculateHValue(i - 1, j, dest);
  239. 				fNew = gNew + hNew;
  240.  
  241. 				// If it isn’t on the open list, add it to
  242. 				// the open list. Make the current square
  243. 				// the parent of this square. Record the
  244. 				// f, g, and h costs of the square cell
  245. 				//			 OR
  246. 				// If it is on the open list already, check
  247. 				// to see if this path to that square is
  248. 				// better, using 'f' cost as the measure.
  249. 				if (cellDetails[i - 1][j].f == FLT_MAX
  250. 					|| cellDetails[i - 1][j].f > fNew) {
  251. 					openList.insert(make_pair(
  252. 						fNew, make_pair(i - 1, j)));
  253.  
  254. 					// Update the details of this cell
  255. 					cellDetails[i - 1][j].f = fNew;
  256. 					cellDetails[i - 1][j].g = gNew;
  257. 					cellDetails[i - 1][j].h = hNew;
  258. 					cellDetails[i - 1][j].parent_i = i;
  259. 					cellDetails[i - 1][j].parent_j = j;
  260. 				}
  261. 			}
  262. 		}
  263.  
  264. 		//----------- 2nd Successor (South) ------------
  265.  
  266. 		// Only process this cell if this is a valid one
  267. 		if (isValid(i + 1, j) == true) {
  268. 			// If the destination cell is the same as the
  269. 			// current successor
  270. 			if (isDestination(i + 1, j, dest) == true) {
  271. 				// Set the Parent of the destination cell
  272. 				cellDetails[i + 1][j].parent_i = i;
  273. 				cellDetails[i + 1][j].parent_j = j;
  274. 				printf("The destination cell is found\n");
  275. 				tracePath(cellDetails, dest);
  276. 				foundDest = true;
  277. 				return;
  278. 			}
  279. 			// If the successor is already on the closed
  280. 			// list or if it is blocked, then ignore it.
  281. 			// Else do the following
  282. 			else if (closedList[i + 1][j] == false
  283. 					&& isUnBlocked(grid, i + 1, j)
  284. 							== true) {
  285. 				gNew = cellDetails[i][j].g + 1.0;
  286. 				hNew = calculateHValue(i + 1, j, dest);
  287. 				fNew = gNew + hNew;
  288.  
  289. 				// If it isn’t on the open list, add it to
  290. 				// the open list. Make the current square
  291. 				// the parent of this square. Record the
  292. 				// f, g, and h costs of the square cell
  293. 				//			 OR
  294. 				// If it is on the open list already, check
  295. 				// to see if this path to that square is
  296. 				// better, using 'f' cost as the measure.
  297. 				if (cellDetails[i + 1][j].f == FLT_MAX
  298. 					|| cellDetails[i + 1][j].f > fNew) {
  299. 					openList.insert(make_pair(
  300. 						fNew, make_pair(i + 1, j)));
  301. 					// Update the details of this cell
  302. 					cellDetails[i + 1][j].f = fNew;
  303. 					cellDetails[i + 1][j].g = gNew;
  304. 					cellDetails[i + 1][j].h = hNew;
  305. 					cellDetails[i + 1][j].parent_i = i;
  306. 					cellDetails[i + 1][j].parent_j = j;
  307. 				}
  308. 			}
  309. 		}
  310.  
  311. 		//----------- 3rd Successor (East) ------------
  312.  
  313. 		// Only process this cell if this is a valid one
  314. 		if (isValid(i, j + 1) == true) {
  315. 			// If the destination cell is the same as the
  316. 			// current successor
  317. 			if (isDestination(i, j + 1, dest) == true) {
  318. 				// Set the Parent of the destination cell
  319. 				cellDetails[i][j + 1].parent_i = i;
  320. 				cellDetails[i][j + 1].parent_j = j;
  321. 				printf("The destination cell is found\n");
  322. 				tracePath(cellDetails, dest);
  323. 				foundDest = true;
  324. 				return;
  325. 			}
  326.  
  327. 			// If the successor is already on the closed
  328. 			// list or if it is blocked, then ignore it.
  329. 			// Else do the following
  330. 			else if (closedList[i][j + 1] == false
  331. 					&& isUnBlocked(grid, i, j + 1)
  332. 							== true) {
  333. 				gNew = cellDetails[i][j].g + 1.0;
  334. 				hNew = calculateHValue(i, j + 1, dest);
  335. 				fNew = gNew + hNew;
  336.  
  337. 				// If it isn’t on the open list, add it to
  338. 				// the open list. Make the current square
  339. 				// the parent of this square. Record the
  340. 				// f, g, and h costs of the square cell
  341. 				//			 OR
  342. 				// If it is on the open list already, check
  343. 				// to see if this path to that square is
  344. 				// better, using 'f' cost as the measure.
  345. 				if (cellDetails[i][j + 1].f == FLT_MAX
  346. 					|| cellDetails[i][j + 1].f > fNew) {
  347. 					openList.insert(make_pair(
  348. 						fNew, make_pair(i, j + 1)));
  349.  
  350. 					// Update the details of this cell
  351. 					cellDetails[i][j + 1].f = fNew;
  352. 					cellDetails[i][j + 1].g = gNew;
  353. 					cellDetails[i][j + 1].h = hNew;
  354. 					cellDetails[i][j + 1].parent_i = i;
  355. 					cellDetails[i][j + 1].parent_j = j;
  356. 				}
  357. 			}
  358. 		}
  359.  
  360. 		//----------- 4th Successor (West) ------------
  361.  
  362. 		// Only process this cell if this is a valid one
  363. 		if (isValid(i, j - 1) == true) {
  364. 			// If the destination cell is the same as the
  365. 			// current successor
  366. 			if (isDestination(i, j - 1, dest) == true) {
  367. 				// Set the Parent of the destination cell
  368. 				cellDetails[i][j - 1].parent_i = i;
  369. 				cellDetails[i][j - 1].parent_j = j;
  370. 				printf("The destination cell is found\n");
  371. 				tracePath(cellDetails, dest);
  372. 				foundDest = true;
  373. 				return;
  374. 			}
  375.  
  376. 			// If the successor is already on the closed
  377. 			// list or if it is blocked, then ignore it.
  378. 			// Else do the following
  379. 			else if (closedList[i][j - 1] == false
  380. 					&& isUnBlocked(grid, i, j - 1)
  381. 							== true) {
  382. 				gNew = cellDetails[i][j].g + 1.0;
  383. 				hNew = calculateHValue(i, j - 1, dest);
  384. 				fNew = gNew + hNew;
  385.  
  386. 				// If it isn’t on the open list, add it to
  387. 				// the open list. Make the current square
  388. 				// the parent of this square. Record the
  389. 				// f, g, and h costs of the square cell
  390. 				//			 OR
  391. 				// If it is on the open list already, check
  392. 				// to see if this path to that square is
  393. 				// better, using 'f' cost as the measure.
  394. 				if (cellDetails[i][j - 1].f == FLT_MAX
  395. 					|| cellDetails[i][j - 1].f > fNew) {
  396. 					openList.insert(make_pair(
  397. 						fNew, make_pair(i, j - 1)));
  398.  
  399. 					// Update the details of this cell
  400. 					cellDetails[i][j - 1].f = fNew;
  401. 					cellDetails[i][j - 1].g = gNew;
  402. 					cellDetails[i][j - 1].h = hNew;
  403. 					cellDetails[i][j - 1].parent_i = i;
  404. 					cellDetails[i][j - 1].parent_j = j;
  405. 				}
  406. 			}
  407. 		}
  408.  
  409. 		//----------- 5th Successor (North-East)
  410. 		//------------
  411.  
  412.         /*
  413. 		// Only process this cell if this is a valid one
  414. 		if (isValid(i - 1, j + 1) == true) {
  415. 			// If the destination cell is the same as the
  416. 			// current successor
  417. 			if (isDestination(i - 1, j + 1, dest) == true) {
  418. 				// Set the Parent of the destination cell
  419. 				cellDetails[i - 1][j + 1].parent_i = i;
  420. 				cellDetails[i - 1][j + 1].parent_j = j;
  421. 				printf("The destination cell is found\n");
  422. 				tracePath(cellDetails, dest);
  423. 				foundDest = true;
  424. 				return;
  425. 			}
  426.  
  427. 			// If the successor is already on the closed
  428. 			// list or if it is blocked, then ignore it.
  429. 			// Else do the following
  430. 			else if (closedList[i - 1][j + 1] == false
  431. 					&& isUnBlocked(grid, i - 1, j + 1)
  432. 							== true) {
  433. 				gNew = cellDetails[i][j].g + 1.414;
  434. 				hNew = calculateHValue(i - 1, j + 1, dest);
  435. 				fNew = gNew + hNew;
  436.  
  437. 				// If it isn’t on the open list, add it to
  438. 				// the open list. Make the current square
  439. 				// the parent of this square. Record the
  440. 				// f, g, and h costs of the square cell
  441. 				//			 OR
  442. 				// If it is on the open list already, check
  443. 				// to see if this path to that square is
  444. 				// better, using 'f' cost as the measure.
  445. 				if (cellDetails[i - 1][j + 1].f == FLT_MAX
  446. 					|| cellDetails[i - 1][j + 1].f > fNew) {
  447. 					openList.insert(make_pair(
  448. 						fNew, make_pair(i - 1, j + 1)));
  449.  
  450. 					// Update the details of this cell
  451. 					cellDetails[i - 1][j + 1].f = fNew;
  452. 					cellDetails[i - 1][j + 1].g = gNew;
  453. 					cellDetails[i - 1][j + 1].h = hNew;
  454. 					cellDetails[i - 1][j + 1].parent_i = i;
  455. 					cellDetails[i - 1][j + 1].parent_j = j;
  456. 				}
  457. 			}
  458. 		}
  459.  
  460. 		//----------- 6th Successor (North-West)
  461. 		//------------
  462.  
  463. 		// Only process this cell if this is a valid one
  464. 		if (isValid(i - 1, j - 1) == true) {
  465. 			// If the destination cell is the same as the
  466. 			// current successor
  467. 			if (isDestination(i - 1, j - 1, dest) == true) {
  468. 				// Set the Parent of the destination cell
  469. 				cellDetails[i - 1][j - 1].parent_i = i;
  470. 				cellDetails[i - 1][j - 1].parent_j = j;
  471. 				printf("The destination cell is found\n");
  472. 				tracePath(cellDetails, dest);
  473. 				foundDest = true;
  474. 				return;
  475. 			}
  476.  
  477. 			// If the successor is already on the closed
  478. 			// list or if it is blocked, then ignore it.
  479. 			// Else do the following
  480. 			else if (closedList[i - 1][j - 1] == false
  481. 					&& isUnBlocked(grid, i - 1, j - 1)
  482. 							== true) {
  483. 				gNew = cellDetails[i][j].g + 1.414;
  484. 				hNew = calculateHValue(i - 1, j - 1, dest);
  485. 				fNew = gNew + hNew;
  486.  
  487. 				// If it isn’t on the open list, add it to
  488. 				// the open list. Make the current square
  489. 				// the parent of this square. Record the
  490. 				// f, g, and h costs of the square cell
  491. 				//			 OR
  492. 				// If it is on the open list already, check
  493. 				// to see if this path to that square is
  494. 				// better, using 'f' cost as the measure.
  495. 				if (cellDetails[i - 1][j - 1].f == FLT_MAX
  496. 					|| cellDetails[i - 1][j - 1].f > fNew) {
  497. 					openList.insert(make_pair(
  498. 						fNew, make_pair(i - 1, j - 1)));
  499. 					// Update the details of this cell
  500. 					cellDetails[i - 1][j - 1].f = fNew;
  501. 					cellDetails[i - 1][j - 1].g = gNew;
  502. 					cellDetails[i - 1][j - 1].h = hNew;
  503. 					cellDetails[i - 1][j - 1].parent_i = i;
  504. 					cellDetails[i - 1][j - 1].parent_j = j;
  505. 				}
  506. 			}
  507. 		}
  508.  
  509. 		//----------- 7th Successor (South-East)
  510. 		//------------
  511.  
  512. 		// Only process this cell if this is a valid one
  513. 		if (isValid(i + 1, j + 1) == true) {
  514. 			// If the destination cell is the same as the
  515. 			// current successor
  516. 			if (isDestination(i + 1, j + 1, dest) == true) {
  517. 				// Set the Parent of the destination cell
  518. 				cellDetails[i + 1][j + 1].parent_i = i;
  519. 				cellDetails[i + 1][j + 1].parent_j = j;
  520. 				printf("The destination cell is found\n");
  521. 				tracePath(cellDetails, dest);
  522. 				foundDest = true;
  523. 				return;
  524. 			}
  525.  
  526. 			// If the successor is already on the closed
  527. 			// list or if it is blocked, then ignore it.
  528. 			// Else do the following
  529. 			else if (closedList[i + 1][j + 1] == false
  530. 					&& isUnBlocked(grid, i + 1, j + 1)
  531. 							== true) {
  532. 				gNew = cellDetails[i][j].g + 1.414;
  533. 				hNew = calculateHValue(i + 1, j + 1, dest);
  534. 				fNew = gNew + hNew;
  535.  
  536. 				// If it isn’t on the open list, add it to
  537. 				// the open list. Make the current square
  538. 				// the parent of this square. Record the
  539. 				// f, g, and h costs of the square cell
  540. 				//			 OR
  541. 				// If it is on the open list already, check
  542. 				// to see if this path to that square is
  543. 				// better, using 'f' cost as the measure.
  544. 				if (cellDetails[i + 1][j + 1].f == FLT_MAX
  545. 					|| cellDetails[i + 1][j + 1].f > fNew) {
  546. 					openList.insert(make_pair(
  547. 						fNew, make_pair(i + 1, j + 1)));
  548.  
  549. 					// Update the details of this cell
  550. 					cellDetails[i + 1][j + 1].f = fNew;
  551. 					cellDetails[i + 1][j + 1].g = gNew;
  552. 					cellDetails[i + 1][j + 1].h = hNew;
  553. 					cellDetails[i + 1][j + 1].parent_i = i;
  554. 					cellDetails[i + 1][j + 1].parent_j = j;
  555. 				}
  556. 			}
  557. 		}
  558.  
  559. 		//----------- 8th Successor (South-West)
  560. 		//------------
  561.  
  562. 		// Only process this cell if this is a valid one
  563. 		if (isValid(i + 1, j - 1) == true) {
  564.             
  565. 			// If the destination cell is the same as the
  566. 			// current successor
  567. 			if (isDestination(i + 1, j - 1, dest) == true) {
  568. 				// Set the Parent of the destination cell
  569. 				cellDetails[i + 1][j - 1].parent_i = i;
  570. 				cellDetails[i + 1][j - 1].parent_j = j;
  571. 				printf("The destination cell is found\n");
  572. 				tracePath(cellDetails, dest);
  573. 				foundDest = true;
  574. 				return;
  575. 			}
  576.  
  577. 			// If the successor is already on the closed
  578. 			// list or if it is blocked, then ignore it.
  579. 			// Else do the following
  580. 			else if (closedList[i + 1][j - 1] == false
  581. 					&& isUnBlocked(grid, i + 1, j - 1)
  582. 							== true) {
  583. 				gNew = cellDetails[i][j].g + 1.414;
  584. 				hNew = calculateHValue(i + 1, j - 1, dest);
  585. 				fNew = gNew + hNew;
  586.  
  587. 				// If it isn’t on the open list, add it to
  588. 				// the open list. Make the current square
  589. 				// the parent of this square. Record the
  590. 				// f, g, and h costs of the square cell
  591. 				//			 OR
  592. 				// If it is on the open list already, check
  593. 				// to see if this path to that square is
  594. 				// better, using 'f' cost as the measure.
  595. 				if (cellDetails[i + 1][j - 1].f == FLT_MAX
  596. 					|| cellDetails[i + 1][j - 1].f > fNew) {
  597. 					openList.insert(make_pair(
  598. 						fNew, make_pair(i + 1, j - 1)));
  599.  
  600. 					// Update the details of this cell
  601. 					cellDetails[i + 1][j - 1].f = fNew;
  602. 					cellDetails[i + 1][j - 1].g = gNew;
  603. 					cellDetails[i + 1][j - 1].h = hNew;
  604. 					cellDetails[i + 1][j - 1].parent_i = i;
  605. 					cellDetails[i + 1][j - 1].parent_j = j;
  606. 				}
  607. 			}
  608. 		}
  609.         */
  610.     }
  611.  
  612. 	// When the destination cell is not found and the open
  613. 	// list is empty, then we conclude that we failed to
  614. 	// reach the destination cell. This may happen when the
  615. 	// there is no way to destination cell (due to
  616. 	// blockages)
  617. 	if (foundDest == false)
  618. 		printf("Failed to find the Destination Cell\n");
  619.  
  620. 	return;
  621. }
  622.  
  623. // Driver program to test above function
  624. int main()
  625. {
  626. 	/* Description of the Grid-
  627. 	1--> The cell is not blocked
  628. 	0--> The cell is blocked */
  629. 	int grid[ROW][COL]
  630. 		= {
  631.         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  632.         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  633.         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  634.         { 0, 0, 0, 0, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  635.         { 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 4171, 4171, 4171, 0, 0, },
  636.         { 0, 4171, 4171, 4171, 0, 0, 4171, 4171, 4171, 0, 4171, 0, 0, 0, 0, },
  637.         { 0, 4171, 4171, 4171, 0, 0, 4171, 4171, 4171, 0, 4171, 0, 0, 0, 0, },
  638.         { 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, },
  639.         { 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 0, 4171, 4171, 0, 0, 0, },
  640.         { 0, 0, 0, 0, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  641.         { 0, 0, 0, 0, 4171, 4171, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  642.         { 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, },
  643.         { 0, 4171, 4171, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, 4171, 4171, 4171, 0, },
  644.         { 0, 0, 0, 0, 4171, 4171, 0, 4171, 0, 0, 0, 4171, 4171, 4171, 0, },
  645.         { 0, 0, 0, 0, 4171, 4171, 0, 4171, 0, 0, 0, 4171, 0, 0, 0, },
  646.         { 0, 0, 0, 0, 4171, 4171, 0, 4171, 4171, 4171, 4171, 4171, 0, 0, 0, },
  647.         { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
  648.     };
  649.  
  650. 	// Source is the left-most bottom-most corner
  651. 	Pair src = make_pair(4, 12);   // invert
  652.  
  653. 	// Destination is the left-most top-most corner
  654. 	Pair dest = make_pair(15, 5);   // invert
  655.  
  656. 	aStarSearch(grid, src, dest);
  657.  
  658. 	return (0);
  659. }
  660.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The destination cell is found

The Path is -> (4,12) -> (4,11) -> (4,10) -> (5,10) -> (6,10) -> (7,10) -> (7,9) -> (7,8) -> (7,7) -> (7,6) -> (7,5) -> (7,4) -> (8,4) -> (9,4) -> (9,5) -> (10,5) -> (11,5) -> (12,5) -> (13,5) -> (13,4) -> (14,4) -> (15,4) -> (15,5)
https://ideone.com/LdKKhI
language:
C++ (gcc 8.3)
created:
13 days 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!