Skip to main content

Find safe place in landmines tracks

The problem is to find a safe path in a landmine field represented by a 2D matrix. The landmine field is represented by a matrix where each cell can either have a landmine (denoted by 0) or be a safe location (denoted by 1). We need to modify the matrix to mark safe paths from safe locations such that all the cells adjacent to a landmine are also marked safe.

Example

Consider the following landmine field represented by a 2D matrix:

1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1

After modifying the matrix to mark safe paths, the new matrix will be:

1 1 1 - - - 1 1 1 1
- - 1 - - - 1 1 - -
- - 1 1 1 1 1 1 - -
- - 1 1 1 1 1 1 - -
1 1 1 1 - - - 1 1 1
1 1 1 1 - - - 1 - -
1 - - - - - - 1 - -
1 - - - 1 1 1 1 - -
1 - - - 1 1 1 1 1 1
1 - - - 1 - - - 1 1
1 1 1 1 1 - - - 1 1

Idea to Solve the Problem

Detect safe place in landmines tracks

To find a safe path in the landmine field, we need to modify the matrix to mark safe locations and avoid unsafe locations (landmines). The idea is to traverse the given matrix and for each landmine found (element with 0 value), we mark all the adjacent cells as safe (element with 1 value). We can consider the adjacent cells in all eight directions.

Pseudocode

changePath(collection, path, r, c, i, j):
    for x from i-1 to i+1:
        for y from j-1 to j+1:
            if x is within range 0 to r-1 and y is within range 0 to c-1:
                path[x][y] = collection[i][j]

findSelfLocation(collection):
    r = number of rows in collection
    c = number of columns in collection
    Create a new matrix 'path' with all elements initialized to 1
    for each i from 0 to r-1:
        for each j from 0 to c-1:
            if collection[i][j] is 0:
                call changePath(collection, path, r, c, i, j)
    print the modified matrix 'path' as safe location

Algorithm Explanation

  1. The changePath function takes the original matrix 'collection', the modified matrix 'path', the number of rows 'r', number of columns 'c', and the current cell indices 'i' and 'j' as input.
  2. It traverses all adjacent cells (8 directions) of the current cell (i, j) and sets the value of the corresponding cells in the modified matrix 'path' to the value of the current cell in the original matrix 'collection'.
  3. The findSelfLocation function takes the original matrix 'collection' as input.
  4. It initializes the modified matrix 'path' with all elements set to 1.
  5. It traverses the original matrix 'collection' and for each landmine found (element with value 0), it calls the changePath function to update the modified matrix 'path'.
  6. The modified matrix 'path' now represents the safe locations, and it is printed as the output.

Code Solution

Here given code implementation process.

/*
    C Program 
    Find safe path in landmines
*/
#include <stdio.h>
#define R 11
#define C 10
// Print location
void printLocation(int matrix[R][C], char landmines) 
{
    for (int i = 0; i < R; ++i) 
    {

        for (int j = 0; j < C; ++j) 
        {
            if(matrix[i][j] == 1)
            {
                printf("  1");
            }
            else
            {
                printf("  %c", landmines); 
            }
        }
        printf("\n");
    }

  printf("\n");
}

// When landmine exists then change adjacent element
void changePath(int collection[R][C],int path[R][C],int i, int j)
{
    int x = 0;
    int y = 0;

    // Set value of possible 8 direction of given i and j
    for (x = i-1; x <= i+1; ++x)
    {
        for (y = j-1; y <= j + 1 ; ++y)
        {
            if(x >= 0 && x < R && y >= 0 && y < C)
            {
                path[x][y] = collection[i][j];
            }
        }
    }
}
// Locate all elements locations that do not activate any landline
void findSelfLocation(int collection[R][C])
{
    
    int path[R][C];
    int i = 0;
    int j = 0;
    // Set default value
    for (i = 0; i < R; ++i)
    {
        for (j = 0; j < C; ++j)
        {
           path[i][j] = 1;
        }
    }

    for (i = 0; i < R; ++i)
    {
        for (j = 0; j < C; ++j)
        {
            if(collection[i][j]==0)
            {
               // landmines found
               changePath(collection,path,i,j);   
            }
        }
    }
 
    printf("\n Given Location \n");
    printLocation(collection,'0');
    printf("\n Safe Location \n");
    printLocation(path,'-');
}

int main()
{
    // Here zero represent landmine locations
    // One indicate a safe position
    int collection[R][C] =
    {
        { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 }
    };
    findSelfLocation(collection);
    
    return 0;
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
/*
   Java Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
    // Print location
    public void printLocation(int[][] matrix,int r, int c, char landmines)
    {
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                if (matrix[i][j] == 1)
                {
                    System.out.print("  1");
                }
                else
                {
                    System.out.print("  " + landmines );
                }
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    // When landmine exists then change adjacent element
    public void changePath(int[][] collection, int[][] path,int r, int c, int i, int j)
    {
        int x = 0;
        int y = 0;
        // Set value of possible 8 direction of given i and j
        for (x = i - 1; x <= i + 1; ++x)
        {
            for (y = j - 1; y <= j + 1; ++y)
            {
                if (x >= 0 && x < r && y >= 0 && y < c)
                {
                    path[x][y] = collection[i][j];
                }
            }
        }
    }
    // Locate all elements locations that do not activate any landline
    public void findSelfLocation(int[][] collection)
    {

        int r = collection.length;
        int c = collection[0].length;
        int[][] path = new int[r][c];
        int i = 0;
        int j = 0;
        // Set default value
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                path[i][j] = 1;
            }
        }
        for (i = 0; i < r; ++i)
        {
            for (j = 0; j < c; ++j)
            {
                if (collection[i][j] == 0)
                {
                    // landmines found
                    changePath(collection, path, r,c, i, j);
                }
            }
        }
        System.out.print("\n Given Location \n");
        printLocation(collection,r,c, '0');
        System.out.print("\n Safe Location \n");
        printLocation(path,r,c, '-');
    }
    public static void main(String[] args) 
    {
        Location task = new Location();

        // Here zero represent landmine locations
        // One indicate a safe position
        int[][] collection =
        {
            { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
            { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
            { 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 }
        };
        task.findSelfLocation(collection);
      
    }
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
// Include header file
#include <iostream>
#define R 11
#define C 10
using namespace std;
/*
   C++ Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
    public:
        // Print location
        void printLocation(int matrix[R][C], char landmines)
        {
            for (int i = 0; i < R; ++i)
            {
                for (int j = 0; j < C; ++j)
                {
                    if (matrix[i][j] == 1)
                    {
                        cout << "  1";
                    }
                    else
                    {
                        cout << "  " << landmines;
                    }
                }
                cout << "\n";
            }
            cout << "\n";
        }
    // When landmine exists then change adjacent element
    void changePath(int collection[R][C], int path[R][C], int i, int j)
    {
        int x = 0;
        int y = 0;
        // Set value of possible 8 direction of given i and j
        for (x = i - 1; x <= i + 1; ++x)
        {
            for (y = j - 1; y <= j + 1; ++y)
            {
                if (x >= 0 && x < R && y >= 0 && y < C)
                {
                    path[x][y] = collection[i][j];
                }
            }
        }
    }
    // Locate all elements locations that do not activate any landline
    void findSelfLocation(int collection[R][C])
    {
        int path[R][C];
        int i = 0;
        int j = 0;
        // Set default value
        for (i = 0; i < R; ++i)
        {
            for (j = 0; j < C; ++j)
            {
                path[i][j] = 1;
            }
        }
        for (i = 0; i < R; ++i)
        {
            for (j = 0; j < C; ++j)
            {
                if (collection[i][j] == 0)
                {
                    // landmines found
                    this->changePath(collection, path, i, j);
                }
            }
        }
        cout << "\n Given Location \n";
        this->printLocation(collection, '0');
        cout << "\n Safe Location \n";
        this->printLocation(path, '-');
    }
};
int main()
{
    Location task = Location();
    // Here zero represent landmine locations
    // One indicate a safe position
    int collection[R][C] =
    {
        { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
        { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 }
    };
    task.findSelfLocation(collection);
    return 0;
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
// Include namespace system
using System;
/*
   C# Program 
   Find safe path in landmines
*/
// Tree Node
public class Location
{
	// Print location
	public void printLocation(int[,] matrix, int r, int c, char landmines)
	{
		for (int i = 0; i < r; ++i)
		{
			for (int j = 0; j < c; ++j)
			{
				if (matrix[i,j] == 1)
				{
					Console.Write("  1");
				}
				else
				{
					Console.Write("  " + landmines);
				}
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	// When landmine exists then change adjacent element
	public void changePath(int[,] collection, int[,] path, int r, int c, int i, int j)
	{
		int x = 0;
		int y = 0;
		// Set value of possible 8 direction of given i and j
		for (x = i - 1; x <= i + 1; ++x)
		{
			for (y = j - 1; y <= j + 1; ++y)
			{
				if (x >= 0 && x < r && y >= 0 && y < c)
				{
					path[x,y] = collection[i,j];
				}
			}
		}
	}
	// Locate all elements locations that do not activate any landline
	public void findSelfLocation(int[,] collection)
	{
		int r = collection.GetLength(0);
		int c = collection.GetLength(1);
		int[,] path = new int[r,c];
		int i = 0;
		int j = 0;
		// Set default value
		for (i = 0; i < r; ++i)
		{
			for (j = 0; j < c; ++j)
			{
				path[i,j] = 1;
			}
		}
		for (i = 0; i < r; ++i)
		{
			for (j = 0; j < c; ++j)
			{
				if (collection[i,j] == 0)
				{
					// landmines found
					changePath(collection, path, r, c, i, j);
				}
			}
		}
		Console.Write("\n Given Location \n");
		printLocation(collection, r, c, '0');
		Console.Write("\n Safe Location \n");
		printLocation(path, r, c, '-');
	}
	public static void Main(String[] args)
	{
		Location task = new Location();
		// Here zero represent landmine locations
		// One indicate a safe position
		int[,] collection = 
       {
          { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
          { 0, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },
          { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
          { 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
          { 1, 1, 1, 1, 1, 1, 0, 1, 1, 1 }
      };
		task.findSelfLocation(collection);
	}
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
<?php
/*
   Php Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
	// Print location
	public	function printLocation( & $matrix, $r, $c, $landmines)
	{
		for ($i = 0; $i < $r; ++$i)
		{
			for ($j = 0; $j < $c; ++$j)
			{
				if ($matrix[$i][$j] == 1)
				{
					echo "  1";
				}
				else
				{
					echo "  ". $landmines;
				}
			}
			echo "\n";
		}
		echo "\n";
	}
	// When landmine exists then change adjacent element
	public	function changePath( & $collection, & $path, $r, $c, $i, $j)
	{
		$x = 0;
		$y = 0;
		// Set value of possible 8 direction of given i and j
		for ($x = $i - 1; $x <= $i + 1; ++$x)
		{
			for ($y = $j - 1; $y <= $j + 1; ++$y)
			{
				if ($x >= 0 && $x < $r && $y >= 0 && $y < $c)
				{
					$path[$x][$y] = $collection[$i][$j];
				}
			}
		}
	}
	// Locate all elements locations that do not activate any landline
	public	function findSelfLocation( & $collection)
	{
		$r = count($collection);
		$c = count($collection[0]);
		$path = array_fill(0, $r, array_fill(0, $c, 1));
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $r; ++$i)
		{
			for ($j = 0; $j < $c; ++$j)
			{
				if ($collection[$i][$j] == 0)
				{
					// landmines found
					$this->changePath($collection, $path, $r, $c, $i, $j);
				}
			}
		}
		echo "\n Given Location \n";
		$this->printLocation($collection, $r, $c, '0');
		echo "\n Safe Location \n";
		$this->printLocation($path, $r, $c, '-');
	}
}

function main()
{
	$task = new Location();
	// Here zero represent landmine locations
	// One indicate a safe position
	$collection = array(
      array(1, 1, 1, 1, 0, 1, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
      array(0, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
      array(1, 1, 1, 1, 1, 0, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
      array(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
      array(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      array(1, 1, 1, 1, 1, 1, 0, 1, 1, 1)
    );
	$task->findSelfLocation($collection);
}
main();

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
/*
   Node Js Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
	// Print location
	printLocation(matrix, r, c, landmines)
	{
		for (var i = 0; i < r; ++i)
		{
			for (var j = 0; j < c; ++j)
			{
				if (matrix[i][j] == 1)
				{
					process.stdout.write("  1");
				}
				else
				{
					process.stdout.write("  " + landmines);
				}
			}
			process.stdout.write("\n");
		}
		process.stdout.write("\n");
	}
	// When landmine exists then change adjacent element
	changePath(collection, path, r, c, i, j)
	{
		var x = 0;
		var y = 0;
		// Set value of possible 8 direction of given i and j
		for (x = i - 1; x <= i + 1; ++x)
		{
			for (y = j - 1; y <= j + 1; ++y)
			{
				if (x >= 0 && x < r && y >= 0 && y < c)
				{
					path[x][y] = collection[i][j];
				}
			}
		}
	}
	// Locate all elements locations that do not activate any landline
	findSelfLocation(collection)
	{
		var r = collection.length;
		var c = collection[0].length;
		var path = Array(r).fill(0).map(() => new Array(c).fill(1));
		var i = 0;
		var j = 0;
		for (i = 0; i < r; ++i)
		{
			for (j = 0; j < c; ++j)
			{
				if (collection[i][j] == 0)
				{
					// landmines found
					this.changePath(collection, path, r, c, i, j);
				}
			}
		}
		process.stdout.write("\n Given Location \n");
		this.printLocation(collection, r, c, '0');
		process.stdout.write("\n Safe Location \n");
		this.printLocation(path, r, c, '-');
	}
}

function main()
{
	var task = new Location();
	// Here zero represent landmine locations
	// One indicate a safe position
	var collection = [
		[1, 1, 1, 1, 0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [0, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
	];
	task.findSelfLocation(collection);
}
main();

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
#    Python 3 Program 
#    Find safe path in landmines

#  Tree Node
class Location :
	#  Print location
	def printLocation(self, matrix, r, c, landmines) :
		i = 0
		while (i < r) :
			j = 0
			while (j < c) :
				if (matrix[i][j] == 1) :
					print("  1", end = "")
				else :
					print(" ", landmines, end = "")
				
				j += 1
			
			print(end = "\n")
			i += 1
		
		print(end = "\n")
	
	#  When landmine exists then change adjacent element
	def changePath(self, collection, path, r, c, i, j) :
		x = i - 1
		y = 0
		#  Set value of possible 8 direction of given i and j
		while (x <= i + 1) :
			y = j - 1
			while (y <= j + 1) :
				if (x >= 0 and x < r and y >= 0 and y < c) :
					path[x][y] = collection[i][j]
				
				y += 1
			
			x += 1
		
	
	#  Locate all elements locations that do not activate any landline
	def findSelfLocation(self, collection) :
		r = len(collection)
		c = len(collection[0])
		path = [[1] * (c) for _ in range(r) ]
		i = 0
		j = 0
		while (i < r) :
			j = 0
			while (j < c) :
				if (collection[i][j] == 0) :
					#  landmines found
					self.changePath(collection, path, r, c, i, j)
				
				j += 1
			
			i += 1
		
		print("\n Given Location ")
		self.printLocation(collection, r, c, '0')
		print("\n Safe Location ")
		self.printLocation(path, r, c, '-')
	

def main() :
	task = Location()
	#  Here zero represent landmine locations
	#  One indicate a safe position
	collection = [
		[1, 1, 1, 1, 0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [0, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
	]
	task.findSelfLocation(collection)

if __name__ == "__main__": main()

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
#    Ruby Program 
#    Find safe path in landmines

#  Tree Node
class Location 
	#  Print location
	def printLocation(matrix, r, c, landmines) 
		i = 0
		while (i < r) 
			j = 0
			while (j < c) 
				if (matrix[i][j] == 1) 
					print("  1")
				else 
					print("  ", landmines)
				end

				j += 1
			end

			print("\n")
			i += 1
		end

		print("\n")
	end

	#  When landmine exists then change adjacent element
	def changePath(collection, path, r, c, i, j) 
		x = i - 1
		y = 0
		#  Set value of possible 8 direction of given i and j
		while (x <= i + 1) 
			y = j - 1
			while (y <= j + 1) 
				if (x >= 0 && x < r && y >= 0 && y < c) 
					path[x][y] = collection[i][j]
				end

				y += 1
			end

			x += 1
		end

	end

	#  Locate all elements locations that do not activate any landline
	def findSelfLocation(collection) 
		r = collection.length
		c = collection[0].length
		path = Array.new(r) {Array.new(c) {1}}
		i = 0
		j = 0
		while (i < r) 
			j = 0
			while (j < c) 
				if (collection[i][j] == 0) 
					#  landmines found
					self.changePath(collection, path, r, c, i, j)
				end

				j += 1
			end

			i += 1
		end

		print("\n Given Location \n")
		self.printLocation(collection, r, c, '0')
		print("\n Safe Location \n")
		self.printLocation(path, r, c, '-')
	end

end

def main() 
	task = Location.new()
	#  Here zero represent landmine locations
	#  One indicate a safe position
	collection = [
		[1, 1, 1, 1, 0, 1, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , [0, 1, 1, 1, 1, 1, 1, 1, 1, 0] , [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 0, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] , [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , [1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
	]
	task.findSelfLocation(collection)
end

main()

Output

 Given Location 
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location 
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1

/*
   Scala Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
	// Print location
	def printLocation(matrix: Array[Array[Int]], r: Int, c: Int, landmines: Char): Unit = {
		var i: Int = 0;
		while (i < r)
		{
			var j: Int = 0;
			while (j < c)
			{
				if (matrix(i)(j) == 1)
				{
					print("  1");
				}
				else
				{
					print("  " + landmines);
				}
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// When landmine exists then change adjacent element
	def changePath(collection: Array[Array[Int]], path: Array[Array[Int]], r: Int, c: Int, i: Int, j: Int): Unit = {
		var x: Int = i - 1;
		var y: Int = 0;
		// Set value of possible 8 direction of given i and j
		while (x <= i + 1)
		{
			y = j - 1;
			while (y <= j + 1)
			{
				if (x >= 0 && x < r && y >= 0 && y < c)
				{
					path(x)(y) = collection(i)(j);
				}
				y += 1;
			}
			x += 1;
		}
	}
	// Locate all elements locations that do not activate any landline
	def findSelfLocation(collection: Array[Array[Int]]): Unit = {
		var r: Int = collection.length;
		var c: Int = collection(0).length;
		var path: Array[Array[Int]] = Array.fill[Int](r, c)(1);
		var i: Int = 0;
		var j: Int = 0;
		while (i < r)
		{
			j = 0;
			while (j < c)
			{
				if (collection(i)(j) == 0)
				{
					// landmines found
					this.changePath(collection, path, r, c, i, j);
				}
				j += 1;
			}
			i += 1;
		}
		print("\n Given Location \n");
		this.printLocation(collection, r, c, '0');
		print("\n Safe Location \n");
		this.printLocation(path, r, c, '-');
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Location = new Location();
		// Here zero represent landmine locations
		// One indicate a safe position
		var collection: Array[Array[Int]] = Array(
          Array(1, 1, 1, 1, 0, 1, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
          Array(0, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 0, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
          Array(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
          Array(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
          Array(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
          Array(1, 1, 1, 1, 1, 1, 0, 1, 1, 1)
        );
		task.findSelfLocation(collection);
	}
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
/*
   Swift 4 Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
	// Print location
	func printLocation(_ matrix: [[Int]], _ r: Int, _ c: Int, _ landmines: Character)
	{
		var i: Int = 0;
		while (i < r)
		{
			var j: Int = 0;
			while (j < c)
			{
				if (matrix[i][j] == 1)
				{
					print("  1", terminator: "");
				}
				else
				{
					print(" ", landmines, terminator: "");
				}
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
		}
		print(terminator: "\n");
	}
	// When landmine exists then change adjacent element
	func changePath(_ collection: [[Int]], _ path: inout[[Int]], _ r: Int, _ c: Int, _ i: Int, _ j: Int)
	{
		var x: Int = i - 1;
		var y: Int = 0;
		// Set value of possible 8 direction of given i and j
		while (x <= i + 1)
		{
			y = j - 1;
			while (y <= j + 1)
			{
				if (x >= 0 && x < r && y >= 0 && y < c)
				{
					path[x][y] = collection[i][j];
				}
				y += 1;
			}
			x += 1;
		}
	}
	// Locate all elements locations that do not activate any landline
	func findSelfLocation(_ collection: [
		[Int]
	])
	{
		let r: Int = collection.count;
		let c: Int = collection[0].count;
		var path: [[Int]] = Array(repeating: Array(repeating: 1, count: c), count: r);
		var i: Int = 0;
		var j: Int = 0;
		while (i < r)
		{
			j = 0;
			while (j < c)
			{
				if (collection[i][j] == 0)
				{
					// landmines found
					self.changePath(collection, &path, r, c, i, j);
				}
				j += 1;
			}
			i += 1;
		}
		print("\n Given Location ");
		self.printLocation(collection, r, c, "0");
		print("\n Safe Location ");
		self.printLocation(path, r, c, "-");
	}
}
func main()
{
	let task: Location = Location();
	// Here zero represent landmine locations
	// One indicate a safe position
	let collection: [[Int]] = [
		[1, 1, 1, 1, 0, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [0, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 0] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 0, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] , 
        [1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
	];
	task.findSelfLocation(collection);
}
main();

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1
/*
   Kotlin Program 
   Find safe path in landmines
*/
// Tree Node
class Location
{
	// Print location
	fun printLocation(matrix: Array <Array<Int>> , r: Int, c: Int, landmines: Char): Unit
	{
		var i: Int = 0;
		while (i < r)
		{
			var j: Int = 0;
			while (j < c)
			{
				if (matrix[i][j] == 1)
				{
					print("  1");
				}
				else
				{
					print("  " + landmines);
				}
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// When landmine exists then change adjacent element
	fun changePath(collection: Array < Array < Int >> , path: Array < Array < Int >> , r: Int, c: Int, i: Int, j: Int): Unit
	{
		var x: Int = i - 1;
		var y: Int = j - 1;
		// Set value of possible 8 direction of given i and j
		while (x <= i + 1)
		{
			
			while (y <= j + 1)
			{
				if (x >= 0 && x < r && y >= 0 && y < c)
				{
					path[x][y] = collection[i][j];
				}
				y += 1;
			}
          	y = j - 1;
			x += 1;
		}
	}
	// Locate all elements locations that do not activate any landline
	fun findSelfLocation(collection: Array<Array<Int>> ): Unit
	{
		var r: Int = collection.count();
		var c: Int = collection[0].count();
		var path: Array < Array < Int >> = Array(r)
		{
			Array(c)
			{
				1
			}
		};
		var i: Int = 0;
		var j: Int = 0;
		while (i < r)
		{
			while (j < c)
			{
				if (collection[i][j] == 0)
				{
					// landmines found
					this.changePath(collection, path, r, c, i, j);
				}
				j += 1;
			}
          	j = 0;
			i += 1;
		}
		print("\n Given Location \n");
		this.printLocation(collection, r, c, '0');
		print("\n Safe Location \n");
		this.printLocation(path, r, c, '-');
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Location = Location();
	// Here zero represent landmine locations
	// One indicate a safe position
	var collection: Array <Array<Int>> = arrayOf(
      arrayOf(1, 1, 1, 1, 0, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(0, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 0, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1, 0), 
      arrayOf(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 0, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 
      arrayOf(1, 1, 1, 1, 1, 1, 0, 1, 1, 1)
    );
	task.findSelfLocation(collection);
}

Output

 Given Location
  1  1  1  1  0  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  0  1  1  1  1  1  1  1  1  0
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  0  1  1  1  1
  1  1  1  1  1  1  1  1  1  0
  1  1  0  1  1  1  1  1  1  1
  1  1  0  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  0  1  1  1


 Safe Location
  1  1  1  -  -  -  1  1  1  1
  -  -  1  -  -  -  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  -  -  1  1  1  1  1  1  -  -
  1  1  1  1  -  -  -  1  1  1
  1  1  1  1  -  -  -  1  -  -
  1  -  -  -  -  -  -  1  -  -
  1  -  -  -  1  1  1  1  -  -
  1  -  -  -  1  1  1  1  1  1
  1  -  -  -  1  -  -  -  1  1
  1  1  1  1  1  -  -  -  1  1

Output Explanation

The above code defines a Location class that finds and prints the safe path in a landmine field represented by a 2D matrix. The output displays the original matrix with 1s representing safe locations and 0s representing landmines, and the modified matrix with '-' representing safe locations.

Original Matrix (landmine field):

1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1

Modified Matrix (safe path):

1 1 1 - - - 1 1 1 1
- - 1 - - - 1 1 - -
- - 1 1 1 1 1 1 - -
- - 1 1 1 1 1 1 - -
1 1 1 1 - - - 1 1 1
1 1 1 1 - - - 1 - -
1 - - - - - - 1 - -
1 - - - 1 1 1 1 - -
1 - - - 1 1 1 1 1 1
1 - - - 1 - - - 1 1
1 1 1 1 1 - - - 1 1

Time Complexity

The time complexity of the provided solution is O(r * c), where 'r' is the number of rows and 'c' is the number of columns in the 2D matrix. The function traverses each element in the matrix once to mark the safe locations. Since each operation takes constant time, the overall time complexity is linear in the size of the matrix.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment