Пошук шляху в лабіринті

Пошук оптимального шляху

 

C#

const int ROW = 4;
const int COL = 5;

// Stores the coordinates
// of the matrix cell
class Point
{
  public int x, y;
  public Point(int x, int y) {
  this.x = x;
  this.y = y;
}
};

// Stores coordinates of
// a cell and its distance
class Node
{
  public Point pt;
  public int dist;
};

static bool isValid(int row, int col)
{
  return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);
}

static int[] dRow = { -1, 0, 0, 1 };
static int[] dCol = { 0, -1, 1, 0 };

static void pathMoves(bool[,] mat, Point src, Point dest)
{
  // Stores the distance for each
  // cell from the source cell
  int[,] d = new int[ROW,COL];
  for (int i = 0; i < ROW; i++)
  {
    for (int j = 0; j < COL; j++)
    {
      d[i, j] = -1;
    }
  }

  // Distance of source cell is 0
  d[src.x,src.y] = 0;

  // Initialize a visited array
  bool[,] visited = new bool[ROW,COL];
  for (int i = 0; i < ROW; i++)
  {
    for (int j = 0; j < COL; j++)
    {
      visited[i, j] = false;
    }
  }

  // Mark source cell as visited
  visited[src.x,src.y] = true;

  // Create a queue for BFS
  Queue<Node> q = new Queue<Node>();

  // Distance of source cell is 0
  Node s = new Node();
  s.pt = src;
  s.dist = 0;

  // Enqueue source cell
  q.Enqueue(s);

  // Keeps track of whether
  // destination is reached or not
  bool ok = false;

  // Iterate until queue is not empty
  while (q.Any())
  {

    // Deque front of the queue
    Node curr = q.Peek();
    Point pt = curr.pt;

    // If the destination cell is
    // reached, then find the path
    if (pt.x == dest.x && pt.y == dest.y)
    {

      int xx = pt.x, yy = pt.y;
      int dist = curr.dist;

      // Assign the distance of
      // destination to the
      // distance matrix
      d[pt.x,pt.y] = dist;

      // Stores the smallest path
      string pathmoves = "";

      // Iterate until source is reached
      while (xx != src.x || yy != src.y)
      {

        // Append D
        if (xx > 0 && d[xx - 1,yy] == dist - 1)
        {
          pathmoves += 'D';
          xx--;
        }

        // Append U
        if (xx < ROW - 1 && d[xx + 1,yy] == dist - 1)
        {
          pathmoves += 'U';
          xx++;
        }

        // Append R
        if (yy > 0 && d[xx,yy - 1] == dist - 1)
        {
          pathmoves += 'R';
          yy--;
        }

        // Append L
        if (yy < COL - 1 && d[xx,yy + 1] == dist - 1)
        {
          pathmoves += 'L';
          yy++;
        }
        dist--;
      }

      // Reverse the backtracked path
      char[] charArray = pathmoves.ToCharArray();
      Array.Reverse(charArray);
      pathmoves = new string(charArray);

      Console.WriteLine(pathmoves);
      ok = true;
      break;
    }

    // Pop the start of queue
    q.Dequeue();

    // Explore all adjacent directions
    for (int i = 0; i < 4; i++)
    {
      int row = pt.x + dRow[i];
      int col = pt.y + dCol[i];

      // If the current cell is valid
      // cell and can be traversed
      if (isValid(row, col) && (mat[row,col] == false) && !visited[row,col])
      {
        // Mark the adjacent cells as visited
        visited[row,col] = true;

        // Enque the adjacent cells
        Node adjCell = new Node();
        Point p = new Point(row, col);
        adjCell.pt = p;
        adjCell.dist = curr.dist + 1;
        q.Enqueue(adjCell);

        // Update the distance
        // of the adjacent cells
        d[row,col] = curr.dist + 1;
      }
    }
  }

  // If the destination
  // is not reachable
  if (!ok)
    Console.WriteLine(-1);
}

static void Main(string[] args)
{
  bool[,] mat = {
    { false, false, false, true, false},
    { false, true, false, true, false},
    { false, true, false, true, false},
    { false, true, false, false, false}
  };
  Point src = new Point(3, 0);
  Point dest = new Point(3, 3);
  pathMoves(mat, src, dest);
  Console.ReadKey();

}

 

UUURRDDDR

 


 

C++

#include <iostream>
#include <queue>

using namespace std;

#define ROW 4
#define COL 5

// Stores the coordinates
// of the matrix cell
struct Point {
  int x, y;
};

// Stores coordinates of
// a cell and its distance
struct Node {
  Point pt;
  int dist;
};

// Check if the given cell is valid or not
bool isValid(int row, int col)
{
  return (row >= 0) && (col >= 0) && (row < ROW) && (col < COL);
}

// Stores the moves of the directions of adjacent cells
int dRow[] = { -1, 0, 0, 1 };
int dCol[] = { 0, -1, 1, 0 };

// Function to find the shortest path from the
// source to destination in the given matrix
void pathMoves(char mat[][COL],
Point src, Point dest)
{
  // Stores the distance for each
  // cell from the source cell
  int d[ROW][COL];
  memset(d, -1, sizeof d);

  // Distance of source cell is 0
  d[src.x][src.y] = 0;

  // Initialize a visited array
  bool visited[ROW][COL];
  memset(visited, false, sizeof visited);

  // Mark source cell as visited
  visited[src.x][src.y] = true;

  // Create a queue for BFS
  queue<Node> q;

  // Distance of source cell is 0
  Node s = { src, 0 };

  // Enqueue source cell
  q.push(s);

  // Keeps track of whether
  // destination is reached or not
  bool ok = false;

  // Iterate until queue is not empty
  while (!q.empty()) {

    // Deque front of the queue
    Node curr = q.front();
    Point pt = curr.pt;

    // If the destination cell is
    // reached, then find the path
    if (pt.x == dest.x && pt.y == dest.y) {

      int xx = pt.x, yy = pt.y;
      int dist = curr.dist;

      // Assign the distance of
      // destination to the
      // distance matrix
      d[pt.x][pt.y] = dist;

      // Stores the smallest path
      string pathmoves = "";

      // Iterate until source is reached
      while (xx != src.x || yy != src.y) {

        // Append D
        if (xx > 0 && d[xx - 1][yy] == dist - 1) {
          pathmoves += 'D';
          xx--;
        }

        // Append U
        if (xx < ROW - 1 && d[xx + 1][yy] == dist - 1) {
          pathmoves += 'U';
          xx++;
        }

        // Append R
        if (yy > 0 && d[xx][yy - 1] == dist - 1) {
          pathmoves += 'R';
          yy--;
        }

        // Append L
        if (yy < COL - 1 && d[xx][yy + 1] == dist - 1) {
          pathmoves += 'L';
          yy++;
        }
        dist--;
      }

      // Reverse the backtracked path
      reverse(pathmoves.begin(),
      pathmoves.end());

      cout << pathmoves;
      ok = true;
      break;
    }

    // Pop the start of queue
    q.pop();

    // Explore all adjacent directions
    for (int i = 0; i < 4; i++) {
      int row = pt.x + dRow[i];
      int col = pt.y + dCol[i];

      // If the current cell is valid
      // cell and can be traversed
      if (isValid(row, col) && (mat[row][col] == '1' || mat[row][col] == 's' 
                             || mat[row][col] == 'd')  && !visited[row][col]) {

        // Mark the adjacent cells as visited
        visited[row][col] = true;

        // Enque the adjacent cells
        Node adjCell = { { row, col }, curr.dist + 1 };
        q.push(adjCell);

        // Update the distance
        // of the adjacent cells
        d[row][col] = curr.dist + 1;
      }
    }
  }

  // If the destination
  // is not reachable
  if (!ok)
  cout << -1;
}

int main()
{
  char mat[ROW][COL] = { { '1', '0', '0', '1', '1'},
                         { '1', '1', '1', '0', '1'},
                         { '0', '1', '0', '0', '1'},
                         { '1', '1', '1', '1', '1'} };
  Point src = { 0, 0 };
  Point dest = { 3, 0 };

  pathMoves(mat, src, dest);

  return 0;
}

DRDDL