# Improving time complexity for Count the Islands DFS

For game AI development, I am currently using a slight modification on the DFS "count the islands" problem (specification below) as a solution to the One Hive Rule for the game of Hive. This may not be the ideal solution so I am open to any other ideas if you note DFS is not the best approach. Thank you.

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

My version utilises a 2D map (matrix) which represents a hexagonal board for the game.

The differences are:

• My implementation uses hexagons so each cell has 6 neighbours, not 8
• Blanks represent 0s and anything else are 1s
• My implementation purposely stops if/when it finds more than one island/hive

My question is can the code be improved with regards to time complexity?

from insects import Blank

class HiveGraph:
def __init__(self, board):
self.row = board.height
self.col = board.width
self.visited = [[False for _ in range(self.col)] for _ in range(self.row)]
self.graph = board.board

# A function to check if a given hexagon can be included in DFS
def is_safe(self, row, col):
# row number is in range,
# column number is in range,
# and hexagon is Blank and not yet visited
return (0 <= row < self.row and
0 <= col < self.col and
not self.visited[row][col] and
type(self.graph[row][col]) is not Blank)

# DFS for a 2D matrix. It only considers
# the 6 neighbours as adjacent pieces
def dfs(self, row, col):
print(row, col)
# These arrays are used to get row and
# column numbers of 6 neighbours
# of a given hexagon
if col % 2 == 1:
row_nbr = [-1,  0, 0,  1, 1, 1]
col_nbr = [ 0, -1, 1, -1, 0, 1]
else:
row_nbr = [-1, -1, -1,  0, 0, 1]
col_nbr = [-1,  0,  1, -1, 1, 0]

# Mark this hexagon as visited
self.visited[row][col] = True

# Recur for all connected neighbours
for k in range(6):
if self.is_safe(row + row_nbr[k], col + col_nbr[k]):
self.dfs(row + row_nbr[k], col + col_nbr[k])

def one_hive(self):
# Initialize count as 0 and traverse
# through the all hexagons of given matrix
count = 0
for row in range(self.row):
for col in range(self.col):
# If a hexagon not Blank and is not visited yet,
# then new hive found
if not self.visited[row][col] and type(self.graph[row][col]) is not Blank:
# Visit all hexagons in this hive
# and increment hive count
count += 1
if count > 1:
return False
self.dfs(row, col)
return True


Refer to this image for row, col matrix values for the layout of hexagons: