const rows = grid.length;
const cols = grid[0].length;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
visited[0][0] = true;
const queue = [[0, 0, 0]];
let head = 0;
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const rows = matrix.length;
const cols = matrix[0].length;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
visited[0][0] = true;
const queue = [[0, 0, 0]];
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const rows = matrix.length;
const cols = matrix[0].length;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
const queue = [];
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (matrix[r][c] === 'S') { queue.push([r, c, 0]); visited[r][c] = true; }
  }
}
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const m = dungeonMap.length;
const n = dungeonMap[0].length;
const queue = [];
for (let r = 0; r < m; r++) {
  for (let c = 0; c < n; c++) {
    if (dungeonMap[r][c] === 0) queue.push([r, c, 0]);
  }
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

const m = matrix.length;
const n = matrix[0].length;
const queue = [];
let humans = 0;
for (let r = 0; r < m; r++) {
  for (let c = 0; c < n; c++) {
    if (matrix[r][c] === 1) queue.push([r, c, 0]);
    else humans += 1;
  }
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let days = 0;

const queue = [start];
const visited = new Set([start]);

const targetX = Math.abs(x);
const targetY = Math.abs(y);
const visited = new Set(['0,0']);
const queue = [[0, 0, 0]];
const moves = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]];

while (head < queue.length) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

while (queue.length > 0) {

  const [r, c, dist] = queue[head++];
  if (grid[r][c] === 9) return dist;

  const [r, c, dist] = queue.shift();
  if (matrix[r][c] === 'X') return dist;

  const [r, c, dist] = queue.shift();
  if (matrix[r][c] === 'X') return dist;

  const [r, c, d] = queue.shift();

  const [r, c, d] = queue.shift();
  days = d;

  const curr = queue.shift();
  if (arr[curr] === 0) return true;

  const [cx, cy, dist] = queue.shift();
  if (cx === targetX && cy === targetY) return dist;

  for (let i = 0; i < 4; i++) {
    const nr = r + dx[i];
    const nc = c + dy[i];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;

  for (let i = 0; i < 4; i++) {
    const nr = r + dx[i];
    const nc = c + dy[i];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;

  for (let i = 0; i < 4; i++) {
    const nr = r + dx[i];
    const nc = c + dy[i];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;

  for (const [dr, dc] of directions) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

  for (const [dr, dc] of directions) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

  for (const next of [curr - arr[curr], curr + arr[curr]]) {

  for (const [dx, dy] of moves) {
    const nx = cx + dx;
    const ny = cy + dy;
    if (nx < -2 || ny < -2 || nx > targetX + 2 || ny > targetY + 2) continue;

    if (visited[nr][nc] || grid[nr][nc] === 1) continue;
    visited[nr][nc] = true;
    queue.push([nr, nc, dist + 1]);

    if (visited[nr][nc] || matrix[nr][nc] === 'D') continue;
    visited[nr][nc] = true;
    queue.push([nr, nc, dist + 1]);

    if (visited[nr][nc] || matrix[nr][nc] === 'D') continue;
    visited[nr][nc] = true;
    queue.push([nr, nc, dist + 1]);

    if (dungeonMap[nr][nc] !== 2147483647) continue;
    dungeonMap[nr][nc] = d + 1;
    queue.push([nr, nc, d + 1]);

    if (matrix[nr][nc] !== 0) continue;
    matrix[nr][nc] = 1;
    humans -= 1;
    queue.push([nr, nc, d + 1]);

    if (next >= 0 && next < arr.length && !visited.has(next)) {
      visited.add(next);
      queue.push(next);
    }

    const key = nx + ',' + ny;
    if (!visited.has(key)) {
      visited.add(key);
      queue.push([nx, ny, dist + 1]);
    }