I have been trying this approach for a little while and keep getting 0 for the count of islands. I am not quite sure what I am doing wrong here. As I have started learning python more and more so I may be missing something that is easy to spot.
So I want to find all the islands with a 1 in them and if they are connected (adjacent cells). So I want to return the count of the number of islands that are found.
Here is what I have so far.
def valid_direction(A, r, c):
row = len(A)
col = len(A[0])
if r < 0 or c < 0 or r >= row or c >= col:
return False
else:
return True
def dfs(A, r, c):
A[r][c] = '1'
# Up down left and right
directions = [(0,1),
(0,-1),
(-1,0),
(1,0)]
for d in directions:
nr = r +d[0]
nc = c + d[1]
if valid_direction(A, nr, nc) and A[nr][nc] == '1':
dfs(A, nr, nc)
def solution(A):
if not A:
return -1
row = len(A)
col = len(A[0])
results = 0
for i in range(row):
for j in range(col):
if A[i][j] == '1':
dfs(A, i, j)
results +=1
return results
And here are the two arrays I am working with
A1 = [[1,1,1,1,0],
[1,1,0,1,0],
[1,1,0,0,0,],
[0,0,0,0,0]]
A2 = [[1,1,0,0,0],
[1,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
You made a simple mistake. Your arrays are arrays of integers, not chars.
A[r][c] = '1' and A[nr][nc] == '1' and if A[i][j] == '1'
should be
A[r][c] = 1 and A[nr][nc] == 1 and if A[i][j] == 1
I'm not sure it will solve the question correctly after this, but this is the current error.
Your current code just counts the number of 1s.
You should check if the 1 is visited ex)by changing it to 2.
Also you don't have to initiate directions every time dfs is called you should just take it outside the function.
directions = [(0,1),
(0,-1),
(-1,0),
(1,0)]
def valid_direction(A, r, c):
row = len(A)
col = len(A[0])
if r < 0 or c < 0 or r >= row or c >= col:
return False
else:
return True
def dfs(A, r, c):
A[r][c] = 2
# Up down left and right
for d in directions:
nr = r +d[0]
nc = c + d[1]
if valid_direction(A, nr, nc) and A[nr][nc] == 1:
dfs(A, nr, nc)
def solution(A):
if not A:
return -1
row = len(A)
col = len(A[0])
results = 0
for i in range(row):
for j in range(col):
if A[i][j] == 1:
dfs(A, i, j)
results +=1
return results
I'm not completely sure what you are trying to solve, but I think the correct code is this.