TryAlgo

Shortest path in a grid

Given a grid with a source cell, a destination cell and obstacle cells, find the shortest path from the source to destination, where every direction change along the path costs 1.

Say the grid has dimensions n times n.

A simple BFS traversal in time \(O(n^3)\)

Consider a graph, where every vertex is a cell of the grid, and there is an edge between two cells of the same column or the same row if they are not separated by an obstacle. Now the problem consists in finding a shortest path in this unweighted graph, and this can be done using a BFS traversal of the graph. There are \(O(n^2)\) vertices and \(O(n)\) edges, which leads to the claimed complexity.

A better analysis shows time is \(O(n^2)\) in fact

When you visit a cell u at distance dist[u] from the source, then you will explore all neighbors: For each of the 8 directions you will explore the cells in that direction at increasing distance from u, and stop once you reached a cell v that is either on the boundary of the grid, or has already been visited. But you can also stop if dist[v] equals dist[u]. Because this means that when later you visit vertex v, anyway you will explore the vertices which are beyond v in the u-v direction.

As a result you will look at a cell v at most 8 times, once for each direction. Hence the algorithm runs in linear time.

#include <cstdio>
#include <utility>
#include <deque>
#include <cstring>

/* Wandering Queen
http://www.spoj.com/problems/QUEEN/

BFS
but be careful in implementation

tricks (don't know if all are necessary)
- store only cells in queue not (cell,direction)
- flatten the grid in a 1 dimensional matrix, so queue can store single integers not pairs
- add border around grid so we can avoid checking boundaries
*/

using namespace std;

#define MAXN 1002

char grid[MAXN * MAXN];                      // too big to be placed on heap
int dist[MAXN * MAXN];


int main() {
  int testcases;
  scanf("%d", &testcases);
  while (testcases-->0) {
    int nr, nc;
    scanf("%d%d", &nr, &nc);                 // read input
    char *p = grid;
    for (int c=0; c < nc + 2; c++)           // add top border
      *p++ = 'X';
    for (int r = 0; r < nr; r++) {
      *p++ = 'X';                            // add left border
      scanf("%s", p);
      p += strlen(p);
      *p++ = 'X';                            // add right border
    }
    for (int c=0; c < nc + 2; c++)           // add bottom border
      *p++ = 'X';
    *p = '\0';                               // mark end of string
    nc += 2;                                 // count for the additional border
    nr += 2;

    int source = strstr(grid, "S") - grid;   // find source

    const int infinity = MAXN * MAXN;        // big enough number
    fill(dist, dist + MAXN * MAXN, infinity);

    //                                       -- direction offsets
    //             E      NE     N      NW    W   SW     S     SE
    int diff[8] = {-1, -1 - nc, -nc, -nc + 1, 1, 1 + nc, nc, nc - 1};

    deque<int> gray;                         // FIFO queue

    dist[source] = 0;                        // start with single source in queue
    gray.push_front(source);

    int answer = -1;                         // default answer if F unreachable from S

    while ( ! gray.empty()) {                // BFS
      int u = gray.front();
      gray.pop_front();

      if (grid[u] == 'F') {                  // target found
        answer = dist[u];
        break;
      }

      for (int a=0; a < 8; a++) {            // look all 8 neighbors
        int v = u;
        while (true) {                       // walk in one direction
          v += diff[a];
          if (grid[v] == 'X' || dist[v] <= dist[u])   // until obstacle reached or already visited
            break;
          if (dist[v] == infinity) {         // new vertex ?
            dist[v] = dist[u] + 1;
            gray.push_back(v);
          }
        }
      }
    }
    printf("%d\n", answer);
  }
  return 0;
}

Improvement through Algorithm A* ?

The algorithm A* is an improvement of the standard Dijkstra shortest path algorithm. All we need is a lower bound on the shortest path to the destination. We model the problem as follows. The queen always stands in some grid cell facing some direction. She can either walk for free one step in her direction or at the cost of 1 unit walk one step in another direction. Suppose that the queen stands in position (0,0) and the destination cell is (x,y). For the lower bound assume that the grid has infinite dimensions and is free of obstacles. Then the queen could reach the destination in 0, 1, or 2 steps, depending on the directions she is currently facing. The cost can be determined through a careful case analysis.

/* Compares (x,y) to the 8 halflines starting at the origin.
   Returns the minimum number of moves the queen must do in order to reach (x,y)
   if she starts at the origin and walks in direction dir.
*/
int heuristic(int x, int y, int dir) {
  // order : NW, N, NE, E, SE, S, SW, W
  bool is_on[8] = { x== -y && x < 0,   y > 0 && x==0,  x == y && x > 0,
                    x == 0 && x > 0, x == -y && x > 0, x == 0 && y < 0,
              x == y && x < 0, y == 0 && x < 0};
  bool is_left[8] = {x > -y, x > 0, x > y, y < 0, x < -y, x < 0, x < y, y > 0};
  // test if (x,y) lies on a halfline
  for(size_t i = 0; i < 8; ++i)
  {
    if (is_on[i]) {
      if (dir == i)
        return 0;
      else if (dir == i + 3 || dir == i + 5)
        return 2;
      else
        return 1;
    }
  }
  // test if (x,y) lies between two halflines
  for(size_t i = 0; i < 8; ++i)
  {
    if (is_left[i] && ! is_left[ (i + 1) % 8]) {
      if (dir == i + 4 || dir == i + 5)
        return 2;
      else
        return 1;
    }
  }
  // this part should never be reached
  return 0;
}

Experiments show that this solution is slower than the BFS described above.