Posted on by Kalkicode
Code Matrix

# 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

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)
{

// 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 }
};

}
}``````

#### 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()
{
// 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 }
};
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)
{
// 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 }
};
}
}``````

#### 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()
{
// 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)
);
}
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()
{
// 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]
];
}
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() :
#  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]
]

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()
#  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]
]
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)
);
}
}``````

#### 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()
{
// 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]
];
}
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
{
// 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)
);
}``````

#### 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.

Categories
Relative Post