[Python][leetcode 733. Flood Field] basic problem

 

📕 Problem

https://leetcode.com/problems/flood-fill/description/

---

💡 My Solution

This is very basic problem for Flood Field.

#leetcode
#733. Flood Fill
# similar wiht find island problem

from collections import deque
import copy

def bfs(y,x,image):
    q = deque()
    q.append((y,x))
    directy = [-1, 1, 0, 0, 0]
    directx = [0, 0, -1, 1, 0]
    while q:
        y, x = q.popleft()
        for i in range(5):
            dy = y + directy[i]
            dx = x + directx[i]
            if dy < 0 or dx < 0 or dy >= m or dx >= n:
                continue
            if visited[dy][dx] != same_color:
                continue
            visited[dy][dx] = 100000
            image[dy][dx] = color
            q.append((dy, dx))


image = [[1,1,1],[1,1,0],[1,0,1]]
# 시작 좌표
sr, sc = 1, 1
color = 2

# row
m = len(image)
# column
n = len(image[0])

same_color = image[sr][sc]
visited = copy.deepcopy(image)
bfs(sr, sc, image)
print(image)

---

✔️ TIL (Today I learned)

When I have a new problem, I have to analyze it well. Because I solved many BFS problems from the same company, I thought that the types of problems were similar. So at first, I thought that this problem was the same, and I solved it in an accustomed way. It looks similar, but the condition is a little bit different. I got the wrong answer in some cases. After that I read the problem again and changed the code a little bit. Reading problems carefully is very important. 

---

💻 Answer

 

▷ Submitted code

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        from collections import deque
        import copy

        def bfs(y,x,image):
            q = deque()
            q.append((y,x))
            directy = [-1, 1, 0, 0, 0]
            directx = [0, 0, -1, 1, 0]
            while q:
                y, x = q.popleft()
                for i in range(5):
                    dy = y + directy[i]
                    dx = x + directx[i]
                    if dy < 0 or dx < 0 or dy >= m or dx >= n:
                        continue
                    if visited[dy][dx] != same_color:
                        continue
                    visited[dy][dx] = 1000000
                    image[dy][dx] = color
                    q.append((dy, dx))
        # row
        m = len(image)
        # column
        n = len(image[0])

        same_color = image[sr][sc]
        visited = copy.deepcopy(image)
        bfs(sr, sc, image)
        return image