fork download
copy 
  1. class Graph: 
  2.  
  3.     def __init__(self, row, col, g): 
  4.         self.ROW = row 
  5.         self.COL = col 
  6.         self.graph = g 
  7.  
  8.     # A function to check if a given cell  
  9.     # (row, col) can be included in DFS 
  10.     def isSafe(self, i, j, visited): 
  11.         # row number is in range, column number 
  12.         # is in range and value is 1  
  13.         # and not yet visited 
  14.         return (i >= 0 and i < self.ROW and 
  15.                 j >= 0 and j < self.COL and 
  16.                 not visited[i][j] and self.graph[i][j]) 
  17.  
  18.  
  19.     # A utility function to do DFS for a 2D  
  20.     # boolean matrix. It only considers 
  21.     # the 8 neighbours as adjacent vertices 
  22.     def DFS(self, i, j, visited): 
  23.  
  24.         # These arrays are used to get row and  
  25.         # column numbers of 8 neighbours  
  26.         # of a given cell 
  27.         rowNbr = [-1, -1, -1,  0, 0,  1, 1, 1]; 
  28.         colNbr = [-1,  0,  1, -1, 1, -1, 0, 1]; 
  29.  
  30.         # Mark this cell as visited 
  31.         visited[i][j] = True
  32.  
  33.         # Recur for all connected neighbours 
  34.         for k in range(8): 
  35.             if self.isSafe(i + rowNbr[k], j + colNbr[k], visited): 
  36.                 self.DFS(i + rowNbr[k], j + colNbr[k], visited) 
  37.  
  38.  
  39.     # The main function that returns 
  40.     # count of islands in a given boolean 
  41.     # 2D matrix 
  42.     def countIslands(self): 
  43.         # Make a bool array to mark visited cells. 
  44.         # Initially all cells are unvisited 
  45.         visited = [[False for j in range(self.COL)]for i in range(self.ROW)] 
  46.  
  47.         # Initialize count as 0 and travese  
  48.         # through the all cells of 
  49.         # given matrix 
  50.         count = 0
  51.         for i in range(self.ROW): 
  52.             for j in range(self.COL): 
  53.                 # If a cell with value 1 is not visited yet,  
  54.                 # then new island found 
  55.                 if visited[i][j] == False and self.graph[i][j] ==1: 
  56.                     # Visit all cells in this island  
  57.                     # and increment island count 
  58.                     self.DFS(i, j, visited) 
  59.                     count += 1
  60.  
  61.         return count 
  62.  
  63. t = int(input())
  64. for x in range(t):
  65.     matrix = []
  66.     row, col = map(int, input().split())
  67.     for i in range(row):
  68.         rows = map(int, input().split())
  69.         print (rows)
  70.         matrix.append(rows)
  71.     print (matrix)
  72.     # g = Graph(row, col, matrix)
  73.     # print (g.countIslands())
Success #stdin #stdout 0.02s 27712KB
comments (?)
stdin
copy 
10
1 1
1
1 1
2
4 2
1 1
2 2
1 1
2 2
3 3
1 2 1
2 1 2
1 2 1
2 2
2 2
2 2
2 2
1 1
1 1
5 5
2 1 1 1 2
1 2 2 2 1
1 2 1 2 1
1 2 2 2 1
2 1 1 1 2
5 5
2 7 9 5 9
3 4 2 3 8
9 9 1 5 6
2 9 7 3 4
3 6 1 7 5
10 10
6 8 7 1 8 2 4 7 2 6
9 3 5 3 8 5 4 6 2 8
5 9 2 8 8 6 4 5 4 8
7 1 9 9 1 9 6 7 4 9
4 2 9 9 6 8 3 9 8 3
6 4 4 3 7 6 6 6 8 6
2 7 3 9 4 5 6 2 6 6
3 3 8 3 5 7 8 7 6 6
7 4 6 6 8 5 3 5 8 9
6 2 9 8 8 9 4 7 2 8
15 15
1 8 8 9 4 4 3 4 3 9 8 6 2 6 6
8 5 6 4 5 2 6 2 5 2 1 5 8 7 5
1 1 6 9 5 6 7 5 3 7 5 2 2 5 9
9 3 3 3 8 2 1 7 5 7 2 1 8 2 1
8 9 7 4 7 9 5 5 2 6 7 4 6 5 7
2 4 2 3 4 6 4 5 8 1 9 6 8 2 8
4 9 1 4 4 8 8 3 9 2 9 7 6 4 3
2 3 3 9 6 2 3 4 9 2 9 8 3 2 4
7 1 8 5 1 4 6 4 2 5 8 7 1 5 3
7 2 6 3 8 2 7 5 1 4 5 9 9 8 2
6 1 2 9 8 7 5 3 9 7 2 7 1 5 2
1 2 7 5 8 4 9 5 8 4 2 3 2 5 2
3 3 4 2 9 5 6 3 8 7 2 1 4 7 1
4 3 9 3 9 5 7 2 4 4 3 7 7 3 5
3 2 1 7 3 5 5 4 9 4 5 7 9 6 3
stdout
copy 
<map object at 0x2af33443e278>
[<map object at 0x2af33443e278>]
<map object at 0x2af33443e390>
[<map object at 0x2af33443e390>]
<map object at 0x2af33443e3c8>
<map object at 0x2af33443e390>
<map object at 0x2af33443e400>
<map object at 0x2af33443e470>
[<map object at 0x2af33443e3c8>, <map object at 0x2af33443e390>, <map object at 0x2af33443e400>, <map object at 0x2af33443e470>]
<map object at 0x2af33443e3c8>
<map object at 0x2af33443e470>
<map object at 0x2af33443e390>
[<map object at 0x2af33443e3c8>, <map object at 0x2af33443e470>, <map object at 0x2af33443e390>]
<map object at 0x2af33443e3c8>
<map object at 0x2af33443e390>
[<map object at 0x2af33443e3c8>, <map object at 0x2af33443e390>]
<map object at 0x2af33443e3c8>
<map object at 0x2af33443e390>
[<map object at 0x2af33443e3c8>, <map object at 0x2af33443e390>]
<map object at 0x2af33443e2e8>
<map object at 0x2af33443e320>
<map object at 0x2af33443e4a8>
<map object at 0x2af33443e438>
<map object at 0x2af33443e518>
[<map object at 0x2af33443e2e8>, <map object at 0x2af33443e320>, <map object at 0x2af33443e4a8>, <map object at 0x2af33443e438>, <map object at 0x2af33443e518>]
<map object at 0x2af33443e390>
<map object at 0x2af33443e4e0>
<map object at 0x2af33443e438>
<map object at 0x2af33443e550>
<map object at 0x2af33443e5c0>
[<map object at 0x2af33443e390>, <map object at 0x2af33443e4e0>, <map object at 0x2af33443e438>, <map object at 0x2af33443e550>, <map object at 0x2af33443e5c0>]
<map object at 0x2af33443e320>
<map object at 0x2af33443e588>
<map object at 0x2af33443e4e0>
<map object at 0x2af33443e470>
<map object at 0x2af33443e400>
<map object at 0x2af33443e630>
<map object at 0x2af33443e6a0>
<map object at 0x2af33443e710>
<map object at 0x2af33443e780>
<map object at 0x2af33443e7f0>
[<map object at 0x2af33443e320>, <map object at 0x2af33443e588>, <map object at 0x2af33443e4e0>, <map object at 0x2af33443e470>, <map object at 0x2af33443e400>, <map object at 0x2af33443e630>, <map object at 0x2af33443e6a0>, <map object at 0x2af33443e710>, <map object at 0x2af33443e780>, <map object at 0x2af33443e7f0>]
<map object at 0x2af33443e518>
<map object at 0x2af33443e7b8>
<map object at 0x2af33443e588>
<map object at 0x2af33443e390>
<map object at 0x2af33443e438>
<map object at 0x2af33443e550>
<map object at 0x2af33443e5f8>
<map object at 0x2af33443e668>
<map object at 0x2af33443e6d8>
<map object at 0x2af33443e748>
<map object at 0x2af33443e860>
<map object at 0x2af33443e908>
<map object at 0x2af33443e9b0>
<map object at 0x2af33443ea58>
<map object at 0x2af33443eb00>
[<map object at 0x2af33443e518>, <map object at 0x2af33443e7b8>, <map object at 0x2af33443e588>, <map object at 0x2af33443e390>, <map object at 0x2af33443e438>, <map object at 0x2af33443e550>, <map object at 0x2af33443e5f8>, <map object at 0x2af33443e668>, <map object at 0x2af33443e6d8>, <map object at 0x2af33443e748>, <map object at 0x2af33443e860>, <map object at 0x2af33443e908>, <map object at 0x2af33443e9b0>, <map object at 0x2af33443ea58>, <map object at 0x2af33443eb00>]
https://ideone.com/bfRaFM
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!