You are given a 2-D array. We have to traverse each and every cell of the given array by following the cell locations then return true else false. The value of each cell is given by (x, y) where (x, y) is also shown next following cell position. Eg. (0, 0) shows starting cell. And ‘null’ shows our final destination after traversing every cell.
Examples:
Input : { 0, 1 1, 2 1, 1
0, 2 2, 0 2, 1
0, 0 1, 0 null }
Output : false
Input : { 0, 1 2, 0
null 1, 0
2, 1 1, 1 }
Output : true
We take a visited array if we visit a cell then make its value true in the visited array so that we can capture the cycle in our grid for next time when we visit it again. And if we find null before completing the loop then it means we didn’t traversed all the cell of given array.
Implementation:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// function which tells all cells are visited or notbool isAllCellTraversed(vector<vector<pair<int,int>>>grid, int n, int m){ bool visited[n][m]; int total = n*m; // starting cell values int startx = grid[0][0].first; int starty = grid[0][0].second; for (int i = 0; i < total - 2; i++) { // if we get {0,0} before the end of loop // then returns false. Because it means we // didn't traverse all the cells if (grid[startx][starty].first == -1 and grid[startx][starty].second == -1) return false; // If found cycle then return false if (visited[startx][starty] == true) return false; visited[startx][starty] = true; int x = grid[startx][starty].first; int y = grid[startx][starty].second; // Update startx and starty values to next // cell values startx = x; starty = y; } // finally if we reach our goal then returns true if (grid[startx][starty].first == -1 and grid[startx][starty].second == -1) return true; return false;}// Driver codeint main(){ vector<vector<pair<int,int>>> cell(3, vector<pair<int,int>> (2)); cell[0][0] = {0, 1}; cell[0][1] = {2, 0}; cell[1][0] = {-1,-1}; cell[1][1] = {1, 0}; cell[2][0] = {2, 1}; cell[2][1] = {1, 1}; if(!isAllCellTraversed(cell, 3, 2)) cout << "true"; else cout << "false"; return 0;}// This code is contributed by mohit kumar 29. |
Java
/* Java program to Find a 2-D array is completelytraversed or not by following the cell values */import java.io.*;class Cell { int x; int y; // Cell class constructor Cell(int x, int y) { this.x = x; this.y = y; }}public class MoveCellPerCellValue { // function which tells all cells are visited or not public boolean isAllCellTraversed(Cell grid[][]) { boolean[][] visited = new boolean[grid.length][grid[0].length]; int total = grid.length * grid[0].length; // starting cell values int startx = grid[0][0].x; int starty = grid[0][0].y; for (int i = 0; i < total - 2; i++) { // if we get null before the end of loop // then returns false. Because it means we // didn't traverse all the cells if (grid[startx][starty] == null) return false; // If found cycle then return false if (visited[startx][starty] == true) return false; visited[startx][starty] = true; int x = grid[startx][starty].x; int y = grid[startx][starty].y; // Update startx and starty values to next // cell values startx = x; starty = y; } // finally if we reach our goal then returns true if (grid[startx][starty] == null) return true; return false; } /* Driver program to test above function */ public static void main(String args[]) { Cell cell[][] = new Cell[3][2]; cell[0][0] = new Cell(0, 1); cell[0][1] = new Cell(2, 0); cell[1][0] = null; cell[1][1] = new Cell(1, 0); cell[2][0] = new Cell(2, 1); cell[2][1] = new Cell(1, 1); MoveCellPerCellValue mcp = new MoveCellPerCellValue(); System.out.println(mcp.isAllCellTraversed(cell)); }} |
Python3
# Python3 program for the above approach# function which tells all cells are visited or notdef isAllCellTraversed(grid, n, m): visited = [[True for j in range(m)] for i in range(n)]; total = n*m; # starting cell values startx = grid[0][0][0]; starty = grid[0][0][1]; for i in range(total-2): # if we get {0,0} before the end of loop # then returns False. Because it means we # didn't traverse all the cells if (grid[startx][starty][0] == -1 and grid[startx][starty][1] == -1): return False; # If found cycle then return False if (visited[startx][starty] == True): return False; visited[startx][starty] = True; x = grid[startx][starty][0]; y = grid[startx][starty][1]; # Update startx and starty values to next # cell values startx = x; starty = y; # finally if we reach our goal then returns True if (grid[startx][starty][0] == -1 and grid[startx][starty][1] == -1): return True; return False; # Driver codecell = [[[] for j in range(3)] for i in range(3)]cell[0][0] = [0, 1];cell[0][1] = [2, 0];cell[1][0] = [-1,-1];cell[1][1] = [1, 0];cell[2][0] = [2, 1];cell[2][1] = [1, 1];if(not isAllCellTraversed(cell, 3, 2)): print("True");else: print("False"); # This code is contributed by rrrtnx. |
C#
/* C# program to Find a 2-D array is completelytraversed or not by following the cell values */using System;public class Cell{ public int x; public int y; // Cell class constructor public Cell(int x, int y) { this.x = x; this.y = y; }}public class MoveCellPerCellValue { // function which tells all cells are visited or not public Boolean isAllCellTraversed(Cell [,]grid) { Boolean[,] visited = new Boolean[grid.GetLength(0), grid.GetLength(1)]; int total = grid.GetLength(0) * grid.GetLength(1); // starting cell values int startx = grid[0, 0].x; int starty = grid[0, 0].y; for (int i = 0; i < total - 2; i++) { // if we get null before the end of loop // then returns false. Because it means we // didn't traverse all the cells if (grid[startx, starty] == null) return false; // If found cycle then return false if (visited[startx, starty] == true) return false; visited[startx, starty] = true; int x = grid[startx, starty].x; int y = grid[startx, starty].y; // Update startx and starty values // to next cell values startx = x; starty = y; } // finally if we reach our goal // then returns true if (grid[startx, starty] == null) return true; return false; } // Driver Code public static void Main(String []args) { Cell [,]cell = new Cell[3, 2]; cell[0, 0] = new Cell(0, 1); cell[0, 1] = new Cell(2, 0); cell[1, 0] = null; cell[1, 1] = new Cell(1, 0); cell[2, 0] = new Cell(2, 1); cell[2, 1] = new Cell(1, 1); MoveCellPerCellValue mcp = new MoveCellPerCellValue(); Console.WriteLine(mcp.isAllCellTraversed(cell)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>/* Javascript program to Find a 2-D array is completelytraversed or not by following the cell values */ class Cell { // Cell class constructor constructor(x,y) { this.x=x; this.y=y; } } // function which tells all // cells are visited or not function isAllCellTraversed(grid) { let visited = new Array(grid.length); for(let i=0;i<visited.length;i++ ) { visited[i]=new Array(grid[0].length); } let total = grid.length * grid[0].length; // starting cell values let startx = grid[0][0].x; let starty = grid[0][0].y; for (let i = 0; i < total - 2; i++) { // if we get null before the end of loop // then returns false. Because it means we // didn't traverse all the cells if (grid[startx][starty] == null) return false; // If found cycle then return false if (visited[startx][starty] == true) return false; visited[startx][starty] = true; let x = grid[startx][starty].x; let y = grid[startx][starty].y; // Update startx and starty // values to next // cell values startx = x; starty = y; } // finally if we reach our goal // then returns true if (grid[startx][starty] == null) return true; return false; } /* Driver program to test above function */ let cell=new Array(3); for(let i=0;i<3;i++) { cell[i]=new Array(2); } cell[0][0] = new Cell(0, 1); cell[0][1] = new Cell(2, 0); cell[1][0] = null; cell[1][1] = new Cell(1, 0); cell[2][0] = new Cell(2, 1); cell[2][1] = new Cell(1, 1); document.write(isAllCellTraversed(cell)); // This code is contributed by unknown2108</script> |
Output
true
Time Complexity : O(N)
Auxiliary Space : O(M*N)
This article is contributed by Harshit Agrawal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
