SlidingPuzzle [source code]
public class SlidingPuzzle {
static
/******************************************************************************/
class Solution {
static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int min_moves = Integer.MAX_VALUE;
public int slidingPuzzle(int[][] board) {
min_moves = Integer.MAX_VALUE; // initialize global var in main function
int[] ar = new int[6];
for (int i = 0; i < 6; i++) {
ar[i] = board[i / 3][i % 3];
}
dfs (ar, new HashMap<> (), 0);
return min_moves == Integer.MAX_VALUE ? -1 : min_moves;
}
void dfs (int[] ar, Map<Integer, Integer> map, int moves) {
if (moves >= min_moves)
return;
int hash = hash (ar);
if (hash == 54321) {
min_moves = moves;
return;
}
if (map.containsKey (hash) && map.get (hash) <= moves)
return;
map.put (hash, moves);
for (int i = 0; i < 6; i++) if (ar[i] == 0) for (int[] incre : increments) {
int x = i / 3 + incre[0], y = i % 3 + incre[1];
if (x >= 0 && y >= 0 && x < 2 && y < 3) {
int index = 3 * x + y;
swap (ar, i, index);
dfs (ar, map, moves + 1);
swap (ar, i, index);
}
}
}
void swap (int[] ar, int i, int j) {
int tmp = ar[i];
ar[i] = ar[j];
ar[j] = tmp;
}
Integer hash (int[] ar) {
int res = 0, base = 1;
for (int i = 0; i < 6; i++) {
res += base * ar[i];
base *= 10;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
SlidingPuzzle.Solution tester = new SlidingPuzzle.Solution();
int[][][] inputs = {
{{1,2,3},{4,0,5}}, {{1}},
{{1,2,3},{5,4,0}}, {{-1}},
{{4,1,2},{5,0,3}}, {{5}},
{{3,2,4},{1,5,0}}, {{14}},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] board = inputs[2 * i];
String input_str = Matrix.printMatrix (board);
int ans = inputs[2 * i + 1][0][0];
System.out.println (Printer.separator ());
int output = tester.slidingPuzzle (board);
System.out.printf ("%s -> %s, expected: %d\n",
input_str, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
static String printBoard (int[] ar) {
StringBuilder sb1 = new StringBuilder (), sb2 = new StringBuilder ();
sb1.append ('\n');
sb2.append ("[[");
for (int i = 0; i < 3; i++) {
sb1.append (ar[i] + " ");
sb2.append (ar[i] + (i < 2 ? "," : ""));
}
sb1.append ('\n');
sb2.append ("],[");
for (int i = 0; i < 3; i++) {
sb1.append (ar[i + 3] + " ");
sb2.append (ar[i + 3] + (i < 2 ? "," : ""));
}
sb1.append ('\n');
sb2.append ("]]");
return sb1.toString () + sb2.toString ();
}
}
大概还是熟悉的一个题目, 每一个node是一个board的state, 然后DFS搜就行了; 注意这里的move的限定比较死, 必须从0位置开始;
一些小技巧应该都是熟悉的, 比如pruning, 然后主函数入口要初始化global var; 然后是hash的计算, 一开始我实际上用的是string的, AC之后就改成integer了, 速度有提升;
核心部分的代码逻辑其实很简单; 这个题目contest当时差点就过了, 最后是因为想错了一个逻辑; 这个当时我去重一开始是用一个set of board states做的, 但是这个不对, 因为你不能因为之前到过一个state就直接ban掉了; 有可能我这一次第二次到访用的moves更少, 所以就应该允许重新搜索; 所以正确的去重应该是用一个Map而不是set; 合理的更新最低的moves, and allow second visit only if you have a better MOVES.
速度是91ms (NA), 一般般; 说起来, airbnb好像就真的是喜欢出这种DFS之类的搜索题目; 按说这个题目其实是可以秒杀的, 还是自己基础不扎实, 这个题目最后的AC rate是50%左右, 可以说算是最仁慈的hard了;
editorial
Approach #1: Breadth-First Search [Accepted]
Intuition
We can think of this problem as a shortest path problem on a graph. Each node is a different board state, and we connect two boards by an edge if they can be transformed into one another in one move. We can solve shortest path problems with breadth first search.
用BFS来找最短路径, 没毛病; 确实比BFS要好一些;
Algorithm
For our breadth first search, we will need to be able to represent the nodes as something hashable, and we'll need to enumerate the neighbors of a board. Afterwards, we can use a typical template for breadth-first search as shown below:
queue = collections.deque([(start, 0)])
seen = {start}
while queue:
node, depth = queue.popleft()
if node == target: return depth
for nei in neighbors(node):
if nei not in seen:
seen.add(nei)
queue.append((nei, depth+1))
To represent the nodes as something hashable, in Python, we convert the board to 1 dimension and use a tuple; in Java we can either encode the board as an integer, or more generally use Arrays.deepToString.
To enumerate the neighbors of a board, we'll remember where the zero is. Then, there are only 4 possible neighbors. If the board is flattened to 1 dimension, these neighbors occur at distances (1, -1, C, -C) from the zero, where C is the number of columns in the board.
class Solution {
public int slidingPuzzle(int[][] board) {
int R = board.length, C = board[0].length;
int sr = 0, sc = 0;
search:
for (sr = 0; sr < R; sr++)
for (sc = 0; sc < C; sc++)
if (board[sr][sc] == 0)
break search;
int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<Node> queue = new ArrayDeque();
Node start = new Node(board, sr, sc, 0);
queue.add(start);
Set<String> seen = new HashSet();
seen.add(start.boardstring);
String target = Arrays.deepToString(new int[][]{{1,2,3}, {4,5,0}});
while (!queue.isEmpty()) {
Node node = queue.remove();
if (node.boardstring.equals(target))
return node.depth;
for (int[] di: directions) {
int nei_r = di[0] + node.zero_r;
int nei_c = di[1] + node.zero_c;
if ((Math.abs(nei_r - node.zero_r) + Math.abs(nei_c - node.zero_c) != 1) ||
nei_r < 0 || nei_r >= R || nei_c < 0 || nei_c >= C)
continue;
int[][] newboard = new int[R][C];
int t = 0;
for (int[] row: node.board)
newboard[t++] = row.clone();
newboard[node.zero_r][node.zero_c] = newboard[nei_r][nei_c];
newboard[nei_r][nei_c] = 0;
Node nei = new Node(newboard, nei_r, nei_c, node.depth+1);
if (seen.contains(nei.boardstring))
continue;
queue.add(nei);
seen.add(nei.boardstring);
}
}
return -1;
}
}
class Node {
int[][] board;
String boardstring;
int zero_r;
int zero_c;
int depth;
Node(int[][] B, int r, int c, int d) {
board = B;
boardstring = Arrays.deepToString(board);
zero_r = r;
zero_c = c;
depth = d;
}
}
这个思路总体还是很简单的, 一个我当时想到但是没有去做的思路, 就是要维护0的位置, 省的每次专门去找, 不过当时的想法是, 其实也就是一个factor of 6, 所以懒得管了;
另外你可能觉得他这里给board专门定义一个class很无聊, 其实这个东西是可能有用的, 就是类似我们当时写earley的时候一样, 这样不仅debug的时候方便(以前说过了), 而且可以用来保存back pointer, 这样可以复原实际的最短路径;
Approach #2: A* Search [Accepted]
Intuition
As in Approach #1, this is a problem about searching on a graph.
We can use the "A* Star Search Algorithm" to search promising nodes in our graph first, with guarantees that it will find the best answer.
这个NLP的时候大概讲过, 这种基于priority的search是safe的: 不会错过optimal, 只要有就一定能够找到;
For every node, we have some estimated cost node.priority = node.depth + node.heuristic, where node.depth is the actual distance travelled, and node.heuristic is our heuristic (guess) of the remaining distance to travel. If the heuristic is admissible (it never overestimates the distance to the goal), then the following algorithm is guaranteed to terminate at the best answer.
For solvers familiar with Dijkstra's Algorithm, A* Search is a special case of Dijkstra's with node.heuristic = 0 always. On certain types of graphs and with good heuristics, this approach is substantially faster then a breadth-first search.
Algorithm
Let's keep a priority queue that sorts by node.depth + node.heuristic. As before, each node represents a puzzle board.
The heuristic we use is the sum of the taxicab distance of each (non-zero) number to it's final destination. This heuristic is admissible as we need at least this many moves.
To speed up our algorithm, we use targetWrong, which has a near zero heuristic distance to the target (meaning our search will aim for it quickly). If it finds it, we don't have to search all the boards.
We could prove that the set of boards can be split in half, with one half transformable to target, and the other half transformable to targetWrong. One way to convince yourself of this is to see that every piece except the last 2 can be placed in the correct position, but a formal proof analyzing the parity of inversions of the underlying permutation is outside the scope of this article. For more information see link.
class Solution {
public int slidingPuzzle(int[][] board) {
int R = board.length, C = board[0].length;
int sr = 0, sc = 0;
//Find sr, sc
search:
for (sr = 0; sr < R; sr++)
for (sc = 0; sc < C; sc++)
if (board[sr][sc] == 0)
break search;
int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
PriorityQueue<Node> heap = new PriorityQueue<Node>((a, b) ->
(a.heuristic + a.depth) - (b.heuristic + b.depth));
Node start = new Node(board, sr, sc, 0);
heap.add(start);
Map<String, Integer> cost = new HashMap();
cost.put(start.boardstring, 9999999);
String target = Arrays.deepToString(new int[][]{{1,2,3}, {4,5,0}});
String targetWrong = Arrays.deepToString(new int[][]{{1,2,3}, {5,4,0}});
while (!heap.isEmpty()) {
Node node = heap.poll();
if (node.boardstring.equals(target))
return node.depth;
if (node.boardstring.equals(targetWrong))
return -1;
if (node.depth + node.heuristic > cost.get(node.boardstring))
continue;
for (int[] di: directions) {
int nei_r = di[0] + node.zero_r;
int nei_c = di[1] + node.zero_c;
// If the neighbor is not on the board or wraps incorrectly around rows/cols
if ((Math.abs(nei_r - node.zero_r) + Math.abs(nei_c - node.zero_c) != 1) ||
nei_r < 0 || nei_r >= R || nei_c < 0 || nei_c >= C)
continue;
int[][] newboard = new int[R][C];
int t = 0;
for (int[] row: node.board)
newboard[t++] = row.clone();
// Swap the elements on the new board
newboard[node.zero_r][node.zero_c] = newboard[nei_r][nei_c];
newboard[nei_r][nei_c] = 0;
Node nei = new Node(newboard, nei_r, nei_c, node.depth+1);
if (nei.depth + nei.heuristic >= cost.getOrDefault(nei.boardstring, 9999999))
continue;
heap.add(nei);
cost.put(nei.boardstring, nei.depth + nei.heuristic);
}
}
return -1;
}
}
class Node {
int[][] board;
String boardstring;
int heuristic;
int zero_r;
int zero_c;
int depth;
Node(int[][] B, int zr, int zc, int d) {
board = B;
boardstring = Arrays.deepToString(board);
//Calculate heuristic
heuristic = 0;
int R = B.length, C = B[0].length;
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
if (board[r][c] == 0) continue;
int v = (board[r][c] + R*C - 1) % (R*C);
// v/C, v%C: where board[r][c] should go in a solved puzzle
heuristic += Math.abs(r - v/C) + Math.abs(c - v%C);
}
heuristic /= 2;
zero_r = zr;
zero_c = zc;
depth = d;
}
}
不过这个算法实际上的WorstCase复杂度并没有得到优化; 但是实际的速度按说是有上升的;
一个复杂算法, 首先还是看了一下geeks4geeks: https://www.geeksforgeeks.org/a-search-algorithm/ . 果然还是有的;
geeks4geeks上面有一句caveat:
Limitations
Although being the best pathfinding algorithm around, A* Search Algorithm doesn’t produce the shortest path always, as it relies heavily on heuristics / approximations to calculate – h
那这个算法还是大概看看就好了, 我还以为是safe的, 真正面试的时候要是heuristic选错了最后做不出来不是蒙蔽; 这个题目, 能想到BFS就已经够好了; DFS还不够, 因为这里的明确目标是找最短, 找最短, BFS是比DFS好的; 比如你看awice上面这个算法, heuristic最后加出来之后, 还专门除了一个2, 这个东西感觉根本就是没有讲究的;
注意他这个操作(board[r][c] + R*C - 1) % (R*C), 是为了从1based的一维坐标转换到0based的, 比如5应该转换到4; 这里写的这么复杂主要是为了处理0这个特殊值, 虽然实际上他这题根本不会出现这个情况: 他自己把0给continue掉了; 后面的一维(0based)index转换到二维这个就是很常规的操作了;
一个重要的东西, 学习这个Arrays.deepToString函数; 这个很重要, 如果实际的面试的时候有print array甚至matrix的需要, 都可以用这个稍微对付一下, 省的自己写了; 而且利用这个写一个好一点的print matrix其实也很快: 没一行调用一下就行了; 不过你说真正面试的时候自己写debug函数会被喷吗? 我认为不应该啊, 反而是反映了实际的实力, 不是吗?
geeks4geeks上面那个A*算法我也附在最后了, 又臭又长. 这里awice这个算法就实际上非常的灵性简练, 实际上看起来跟一个普通的BFS很像. 事实上, BFS其实也是有一定的priority性质在里面的, 不是吗?
注意, geeks4geeks讨论A*和DJ算法的时候, 是提到了一个open list and closed list的, 就有点像CLRS上面用的涂色来代表状态(是否处理过了). 这里awice的算法实际上并不难理解, 正常的一个类似BFS的queue-based的算法写法就行了: Poll一个当前的, 然后最后记得conditional add children之类的;
discussion最优解:
@rock said in Java 19ms 28 clean lines BFS with comment.:
Convert array to string, e.g., [[1,2,3],[4,0,5]] -> "123405", hence the corresponding potential swap distances are: -1, 1, -3, 3. Also note, charAt(2) and charAt(3) are not adjacent in original 2 dimensional int array and therefore are not valid swaps.
public int slidingPuzzle(int[][] board) {
Set<String> seen = new HashSet<>(); // used to avoid duplicates
String target = "123450";
// convert board to string - initial state.
String s = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
Queue<String> q = new LinkedList<>(Arrays.asList(s));
seen.add(s);
int ans = 0; // record the # of rounds of Breadth Search
while (!q.isEmpty()) { // Not traverse all states yet?
// loop used to control search breadth.
for (int sz = q.size(); sz > 0; --sz) {
String str = q.poll();
if (str.equals(target)) { return ans; } // found target.
int i = str.indexOf('0'); // locate '0'
int[] d = { 1, -1, 3, -3 }; // potential swap distances.
for (int k = 0; k < 4; ++k) { // traverse all options.
int j = i + d[k]; // potential swap index.
// conditional used to avoid invalid swaps.
if (j < 0 || j > 5 || i == 2 && j == 3 || i == 3 && j == 2) { continue; }
char[] ch = str.toCharArray();
// swap ch[i] and ch[j].
char tmp = ch[i];
ch[i] = ch[j];
ch[j] = tmp;
s = String.valueOf(ch); // a new candidate state.
if (seen.add(s)) { q.offer(s); } //Avoid duplicate.
}
}
++ans; // finished a round of Breadth Search, plus 1.
}
return -1;
}
之前看editorial的时候漏掉一个点, 实际上BFS的话, 用set是没问题的, 因为是一个按照moves/depth前进的过程, 所以不会导致说新来的moves还比上一次到这里的时候的moves少;
discussion也有一个写A*的, 没时间看了:
@invalid said in Simple Python solution using A* search:
Same A* but implemented in lengthy Java
public int slidingPuzzle(int[][] a) {
int[][] moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
PriorityQueue<State> pq = new PriorityQueue<>();
Set<State> been = new HashSet<>();
int zi = 0, zj = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (a[i][j] == 0) {
zi = i;
zj = j;
break;
}
}
}
State start = new State(a, 0, zi, zj);
pq.add(start);
been.add(start);
while (!pq.isEmpty()) {
State pop = pq.remove();
if (pop.isGoal()) return pop.taken;
for (int[] move : moves) {
int nzi = pop.zi + move[0];
int nzj = pop.zj + move[1];
State newState = pop.swap(nzi, nzj);
if (newState == null || been.contains(newState)) continue;
been.add(newState);
pq.add(newState);
}
}
return -1;
}
private static class State implements Comparable<State> {
int[][] a;
int taken;
int zi, zj;
public State(int[][] a, int taken, int zi, int zj) {
this.a = new int[2][3];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) this.a[i][j] = a[i][j];
}
this.taken = taken;
this.zi = zi;
this.zj = zj;
}
public State swap(int i, int j) {
if (i < 0 || i >= 2 || j < 0 || j >= 3) return null;
State res = new State(this.a, this.taken + 1, i, j);
int temp = res.a[i][j];
res.a[i][j] = res.a[zi][zj];
res.a[zi][zj] = temp;
return res;
}
public int distance() {
int res = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
if (a[i][j] == 0) continue;
int val = a[i][j] - 1;
int si = val / 3;
int sj = val % 3;
res += Math.abs(si - i) + Math.abs(sj - j);
}
}
return res;
}
public boolean isGoal() {
return distance() == 0;
}
@Override
public boolean equals(Object obj) {
State that = (State) obj;
return Arrays.deepEquals(this.a, that.a);
}
@Override
public int hashCode() {
return Arrays.deepHashCode(a);
}
@Override
public int compareTo(State that) {
return this.distance() + taken - that.distance() - that.taken;
}
}
没有submission;
Problem Description
On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Examples:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]]
Output: 14
Note:
- board will be a 2 x 3 array as described above.
- board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].
Difficulty:Hard
Total Accepted:870
Total Submissions:1.7K
Contributor:awice
Companies
airbnb
Related Topics
breadth-first search
Hint 1
Perform a breadth-first-search, where the nodes are the puzzle boards and edges are if two puzzle boards can be transformed into one another with one move.
Problem Description
最后专门贴一个geeks4geeks上面那个A*算法:
// A C++ Program to implement A* Search Algorithm
#include<bits/stdc++.h>
using namespace std;
#define ROW 9
#define COL 10
// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int>> pPair;
// A structure to hold the neccesary parameters
struct cell
{
// Row and Column index of its parent
// Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
int parent_i, parent_j;
// f = g + h
double f, g, h;
};
// A Utility Function to check whether given cell (row, col)
// is a valid cell or not.
bool isValid(int row, int col)
{
// Returns true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// A Utility Function to check whether the given cell is
// blocked or not
bool isUnBlocked(int grid[][COL], int row, int col)
{
// Returns true if the cell is not blocked else false
if (grid[row][col] == 1)
return (true);
else
return (false);
}
// A Utility Function to check whether destination cell has
// been reached or not
bool isDestination(int row, int col, Pair dest)
{
if (row == dest.first && col == dest.second)
return (true);
else
return (false);
}
// A Utility Function to calculate the 'h' heuristics.
double calculateHValue(int row, int col, Pair dest)
{
// Return using the distance formula
return ((double)sqrt ((row-dest.first)*(row-dest.first)
+ (col-dest.second)*(col-dest.second)));
}
// A Utility Function to trace the path from the source
// to destination
void tracePath(cell cellDetails[][COL], Pair dest)
{
printf ("\nThe Path is ");
int row = dest.first;
int col = dest.second;
stack<Pair> Path;
while (!(cellDetails[row][col].parent_i == row
&& cellDetails[row][col].parent_j == col ))
{
Path.push (make_pair (row, col));
int temp_row = cellDetails[row][col].parent_i;
int temp_col = cellDetails[row][col].parent_j;
row = temp_row;
col = temp_col;
}
Path.push (make_pair (row, col));
while (!Path.empty())
{
pair<int,int> p = Path.top();
Path.pop();
printf("-> (%d,%d) ",p.first,p.second);
}
return;
}
// A Function to find the shortest path between
// a given source cell to a destination cell according
// to A* Search Algorithm
void aStarSearch(int grid[][COL], Pair src, Pair dest)
{
// If the source is out of range
if (isValid (src.first, src.second) == false)
{
printf ("Source is invalid\n");
return;
}
// If the destination is out of range
if (isValid (dest.first, dest.second) == false)
{
printf ("Destination is invalid\n");
return;
}
// Either the source or the destination is blocked
if (isUnBlocked(grid, src.first, src.second) == false ||
isUnBlocked(grid, dest.first, dest.second) == false)
{
printf ("Source or the destination is blocked\n");
return;
}
// If the destination cell is the same as source cell
if (isDestination(src.first, src.second, dest) == true)
{
printf ("We are already at the destination\n");
return;
}
// Create a closed list and initialise it to false which means
// that no cell has been included yet
// This closed list is implemented as a boolean 2D array
bool closedList[ROW][COL];
memset(closedList, false, sizeof (closedList));
// Declare a 2D array of structure to hold the details
//of that cell
cell cellDetails[ROW][COL];
int i, j;
for (i=0; i<ROW; i++)
{
for (j=0; j<COL; j++)
{
cellDetails[i][j].f = FLT_MAX;
cellDetails[i][j].g = FLT_MAX;
cellDetails[i][j].h = FLT_MAX;
cellDetails[i][j].parent_i = -1;
cellDetails[i][j].parent_j = -1;
}
}
// Initialising the parameters of the starting node
i = src.first, j = src.second;
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent_i = i;
cellDetails[i][j].parent_j = j;
// Create an open list having information as-
// <f, <i, j>>
// where f = g + h,
// and i, j are the row and column index of that cell
// Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
// This open list is implenented as a set of pair of pair.
set<pPair> openList;
// Put the starting cell on the open list and set its
// 'f' as 0
openList.insert(make_pair (0.0, make_pair (i, j)));
// We set this boolean value as false as initially
// the destination is not reached.
bool foundDest = false;
while (!openList.empty())
{
pPair p = *openList.begin();
// Remove this vertex from the open list
openList.erase(openList.begin());
// Add this vertex to the open list
i = p.second.first;
j = p.second.second;
closedList[i][j] = true;
// Generating all the 8 successor of this cell
// N.W N N.E
// \ | /
// \ | /
// W----Cell----E
// / | \
// / | \
// S.W S S.E
// Cell-->Popped Cell (i, j)
// N --> North (i-1, j)
// S --> South (i+1, j)
// E --> East (i, j+1)
// W --> West (i, j-1)
// N.E--> North-East (i-1, j+1)
// N.W--> North-West (i-1, j-1)
// S.E--> South-East (i+1, j+1)
// S.W--> South-West (i+1, j-1)
// To store the 'g', 'h' and 'f' of the 8 successors
double gNew, hNew, fNew;
//----------- 1st Successor (North) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j] == false &&
isUnBlocked(grid, i-1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i-1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j].f == FLT_MAX ||
cellDetails[i-1][j].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair(i-1, j)));
// Update the details of this cell
cellDetails[i-1][j].f = fNew;
cellDetails[i-1][j].g = gNew;
cellDetails[i-1][j].h = hNew;
cellDetails[i-1][j].parent_i = i;
cellDetails[i-1][j].parent_j = j;
}
}
}
//----------- 2nd Successor (South) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j] == false &&
isUnBlocked(grid, i+1, j) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i+1, j, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j].f == FLT_MAX ||
cellDetails[i+1][j].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i+1, j)));
// Update the details of this cell
cellDetails[i+1][j].f = fNew;
cellDetails[i+1][j].g = gNew;
cellDetails[i+1][j].h = hNew;
cellDetails[i+1][j].parent_i = i;
cellDetails[i+1][j].parent_j = j;
}
}
}
//----------- 3rd Successor (East) ------------
// Only process this cell if this is a valid one
if (isValid (i, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j+1] == false &&
isUnBlocked (grid, i, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue (i, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j+1].f == FLT_MAX ||
cellDetails[i][j+1].f > fNew)
{
openList.insert( make_pair(fNew,
make_pair (i, j+1)));
// Update the details of this cell
cellDetails[i][j+1].f = fNew;
cellDetails[i][j+1].g = gNew;
cellDetails[i][j+1].h = hNew;
cellDetails[i][j+1].parent_i = i;
cellDetails[i][j+1].parent_j = j;
}
}
}
//----------- 4th Successor (West) ------------
// Only process this cell if this is a valid one
if (isValid(i, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i][j-1] == false &&
isUnBlocked(grid, i, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(i, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i][j-1].f == FLT_MAX ||
cellDetails[i][j-1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair (i, j-1)));
// Update the details of this cell
cellDetails[i][j-1].f = fNew;
cellDetails[i][j-1].g = gNew;
cellDetails[i][j-1].h = hNew;
cellDetails[i][j-1].parent_i = i;
cellDetails[i][j-1].parent_j = j;
}
}
}
//----------- 5th Successor (North-East) ------------
// Only process this cell if this is a valid one
if (isValid(i-1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i-1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j+1] == false &&
isUnBlocked(grid, i-1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j+1].f == FLT_MAX ||
cellDetails[i-1][j+1].f > fNew)
{
openList.insert( make_pair (fNew,
make_pair(i-1, j+1)));
// Update the details of this cell
cellDetails[i-1][j+1].f = fNew;
cellDetails[i-1][j+1].g = gNew;
cellDetails[i-1][j+1].h = hNew;
cellDetails[i-1][j+1].parent_i = i;
cellDetails[i-1][j+1].parent_j = j;
}
}
}
//----------- 6th Successor (North-West) ------------
// Only process this cell if this is a valid one
if (isValid (i-1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination (i-1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i-1][j-1] == false &&
isUnBlocked(grid, i-1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i-1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i-1][j-1].f == FLT_MAX ||
cellDetails[i-1][j-1].f > fNew)
{
openList.insert( make_pair (fNew, make_pair (i-1, j-1)));
// Update the details of this cell
cellDetails[i-1][j-1].f = fNew;
cellDetails[i-1][j-1].g = gNew;
cellDetails[i-1][j-1].h = hNew;
cellDetails[i-1][j-1].parent_i = i;
cellDetails[i-1][j-1].parent_j = j;
}
}
}
//----------- 7th Successor (South-East) ------------
// Only process this cell if this is a valid one
if (isValid(i+1, j+1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j+1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
printf ("The destination cell is found\n");
tracePath (cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j+1] == false &&
isUnBlocked(grid, i+1, j+1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j+1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j+1].f == FLT_MAX ||
cellDetails[i+1][j+1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair (i+1, j+1)));
// Update the details of this cell
cellDetails[i+1][j+1].f = fNew;
cellDetails[i+1][j+1].g = gNew;
cellDetails[i+1][j+1].h = hNew;
cellDetails[i+1][j+1].parent_i = i;
cellDetails[i+1][j+1].parent_j = j;
}
}
}
//----------- 8th Successor (South-West) ------------
// Only process this cell if this is a valid one
if (isValid (i+1, j-1) == true)
{
// If the destination cell is the same as the
// current successor
if (isDestination(i+1, j-1, dest) == true)
{
// Set the Parent of the destination cell
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
printf("The destination cell is found\n");
tracePath(cellDetails, dest);
foundDest = true;
return;
}
// If the successor is already on the closed
// list or if it is blocked, then ignore it.
// Else do the following
else if (closedList[i+1][j-1] == false &&
isUnBlocked(grid, i+1, j-1) == true)
{
gNew = cellDetails[i][j].g + 1.414;
hNew = calculateHValue(i+1, j-1, dest);
fNew = gNew + hNew;
// If it isn’t on the open list, add it to
// the open list. Make the current square
// the parent of this square. Record the
// f, g, and h costs of the square cell
// OR
// If it is on the open list already, check
// to see if this path to that square is better,
// using 'f' cost as the measure.
if (cellDetails[i+1][j-1].f == FLT_MAX ||
cellDetails[i+1][j-1].f > fNew)
{
openList.insert(make_pair(fNew,
make_pair(i+1, j-1)));
// Update the details of this cell
cellDetails[i+1][j-1].f = fNew;
cellDetails[i+1][j-1].g = gNew;
cellDetails[i+1][j-1].h = hNew;
cellDetails[i+1][j-1].parent_i = i;
cellDetails[i+1][j-1].parent_j = j;
}
}
}
}
// When the destination cell is not found and the open
// list is empty, then we conclude that we failed to
// reach the destiantion cell. This may happen when the
// there is no way to destination cell (due to blockages)
if (foundDest == false)
printf("Failed to find the Destination Cell\n");
return;
}
// Driver program to test above function
int main()
{
// Description of the Grid-
// 1--> The cell is not blocked
// 0--> The cell is blocked
int grid[ROW][COL] =
{
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }
};
// Source is the left-most bottom-most corner
Pair src = make_pair(8, 0);
// Destination is the left-most top-most corner
Pair dest = make_pair(0, 0);
aStarSearch(grid, src, dest);
return(0);
}
这个程序大概看看就行了, 写的比较的厚重, 一点小东西都要factor成一个utility; 当然了, 从长期开发的角度来说,是好习惯没错了; 大概扫了一眼, 太啰嗦了, 懒得看了;