Shortest path between two cells in a matrix

main.dart

import 'dart:collection';

class Point {
  int x;
  int y;
  Point({required this.y,required this.x});
}

void main() {
  print('Finding a viable solution for the shortest path...');
  
  var grid = [
    ['🌿','🌿','🌿','🌿','🌿'],
    ['🌿','🌿','🌿','🌿','🌿'],
    ['🌊','🌿','🌊','🌿','🌿'], // Character is at position grid[2][1]
    ['🌿','🌿','🌊','🌿','🌿'], // Destination is position grid[2][3]
    ['🌿','🌿','🌿','🌿','🌿'],
  ];
  
  var characterPosition = Point(y: 2, x: 1);
  var characterDestination = Point(y: 2, x: 3);
  
  PathFinder pathFinder = PathFinder(grid, characterPosition, characterDestination);
  if (pathFinder.solutionExists) {
    print('...Solution exists!');
    for (Point point in pathFinder.solution) {
      print('(${point.y},${point.x})');
    }
  }
  else {
    print('...No solution exists.');
  }
}

class PathFinder {
  late Queue<Point> solution;
  late bool solutionExists;

  PathFinder(grid, characterPosition, characterDestination) {

    // Applying BFS on matrix cells.
    Queue<Point> queue = Queue<Point>();
    queue.add(new Point(y: characterPosition.y, x: characterPosition.x));

    List<List<bool>> visited = List.generate(
      grid.length,
      (index) => List.generate(
        grid[0].length,
        (index) => false,
        growable: false,
      ),
      growable: false,
    );

    visited[characterPosition.y][characterPosition.x] =
        true;

    while (queue.isNotEmpty) {
      Point point = queue.removeLast();

      // Destination found
      if (point.x == characterDestination.x &&
          point.y == characterDestination.y) {
        this.solutionExists = true;
        this.solution = queue;
        return;
      }

      // moving up
      if (_isValid(x: point.x, y: point.y - 1, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y - 1, x: point.x));
        visited[point.y - 1][point.x] = true;
      }

      // moving down
      if (_isValid(x: point.x, y: point.y + 1, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y + 1, x: point.x));
        visited[point.y + 1][point.x] = true;
      }

      // moving left
      if (_isValid(x: point.x - 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y, x: point.x - 1));
        visited[point.y][point.x - 1] = true;
      }

      // moving right
      if (_isValid(x: point.x + 1, y: point.y, grid: grid, visited: visited)) {
        queue.add(new Point(y: point.y, x: point.x + 1));
        visited[point.y][point.x + 1] = true;
      }
    }

    this.solutionExists = false;
    this.solution = queue;
    return;
  }

  bool _isValid({required int x, required int y, required List<List<String>> grid, required List<List<bool>> visited}) {
    if (x >= 0 &&
        y >= 0 &&
        x < grid[0].length &&
        y < grid.length &&
        grid[y][x] != '🌊' &&
        visited[y][x] == false) {
      return true;
    }
    return false;
  }
}