не в состоянии отследить серую клетку в лабиринте

Существует матрица, которая содержит белые ячейки (представленные как 1), черные ячейки (представленные как 0) и только одну серую ячейку (обозначенную как 2), необходимо перейти от (0,0) к (N-1, N-1) ) в массиве [N] [N].

Ограничения:

1) Путь должен охватывать только белые ячейки и проходить через серую ячейку (эта серая ячейка может находиться в любом месте массива)

2) Один раз посещенный узел не может быть снова посещен.

Ниже приведено типичное решение лабиринтной задачи, но это решение не обрабатывает конкретный случай обхода ячейки GREY … поэтому, пожалуйста, помогите мне изменить приведенный ниже код для обработки конкретного случая.

Моя проблема в том, что я не уверен, как поставить чек на серую ячейку?

#include "stdafx.h"#include "algorithm"#include <iostream>
#include <fstream>
using namespace std;
#include<stdio.h>

// Maze size
#define N 4

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("\n");
}
}

/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
//solveMazeUtil() to solve the problem. It returns false if no path is possible,
//otherwise return true and prints the path in the form of 1s. Please note that
//there may be more than one solutions, this function prints one of the feasible
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
// if (x,y outside maze) return false
return true;

return false;
}

/* This function solves the Maze problem using Backtracking. It mainly uses
solutions.*/
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};

if(solveMazeUtil(maze, 0, 0, sol) == false)
{
printf("Solution doesn't exist");
return false;
}

printSolution(sol);
return true;
}

/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;

/* Move forward in x direction */
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;

/* If x moving in x direction doesn't give solution then
Move down in y direction */
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;

/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
return false;
}

return false;
}

// driver program to test above function
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};

solveMaze(maze);
getchar();
return 0;
}

Одно из решений, о котором я думаю:

Создайте все возможные пути (которые проходят через 1 или 2).

Затем выясните, какой из путей имеет 2 в нем. а затем распечатать этот путь в качестве вывода.

Но я не думаю, что это будет хороший подход … Итак, пожалуйста, дайте мне знать, как достичь своей цели достойным образом.
Спасибо