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 1After 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 1Idea 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 locationAlgorithm Explanation
- The
changePathfunction 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. - 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'.
- The
findSelfLocationfunction takes the original matrix 'collection' as input. - It initializes the modified matrix 'path' with all elements set to 1.
- It traverses the original matrix 'collection' and for each landmine found (element with value 0), it calls the
changePathfunction to update the modified matrix 'path'. - 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 1Modified 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 1Time 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.
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