733. Flood Fill

مسئله:پر کردن سیل‌آسا (Flood Fill) در تصویر

فرض کنید یک تصویر با ابعاد m × n به صورت یک ماتریس از اعداد صحیح به نام image نمایش داده شده است، که در آن image[i][j] نشان‌دهنده مقدار پیکسل در آن مکان ( مختصات i, j) است.

همچنین سه عدد صحیح دیگر به نام‌های sr، sc و color به شما داده شده است. شما باید بر روی این تصویر با شروع از پیکسل image[sr][sc] یک پر کردن سیل‌آسا (flood fill) انجام دهید.

برای انجام پر کردن سیل‌آسا، پیکسل شروع را در نظر بگیرید، به همراه هر پیکسلی که به صورت چهار جهتی (بالا، پایین، چپ، راست) به پیکسل شروع متصل است و رنگ آن با پیکسل شروع یکسان است، به علاوه هر پیکسلی که به صورت چهار جهتی به آن پیکسل‌ها متصل است (همچنین با رنگ یکسان) و به همین ترتیب ادامه دهید. رنگ تمام پیکسل‌های ذکر شده را با color جایگزین کنید.

خروجی: تصویر اصلاح شده بعد از انجام پر کردن سیل‌آسا (Flood Fill) را برگردانید.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: The starting pixel is already colored 0, so no changes are made to the image.

قیدها:

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2×16
• 0 <= sr < m
• 0 <= sc < n

راه حل: با استفاده از DFS

روش نوشتن DFS نسبتاً ساده است، ابتدا فرض می‌شود که اگر رنگ موقعیت داده شده با رنگ جدید یکی باشد، در غیر این صورت تابع بازگشتی برای موقعیت داده شده فراخوانی می‌شود. در تابع بازگشتی، اگر از محدوده خارج شود یا رنگ فعلی با رنگ شروع متفاوت باشد، نتیجه مستقیماً برمی‌گردد. در غیر این صورت، یک‌رنگ جدید به موقعیت فعلی اختصاص دهید، و سپس به فراخوانی تابع بازگشتی در چهار نقطه اطراف ادامه دهید.

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
 oc := image[sr][sc]
 m, n := len(image), len(image[0])
 dirs := []int{-1, 0, 1, 0, -1}
 var dfs func(i, j int)
 dfs = func(i, j int) {
  if i < 0 || i >= m || j < 0 || j >= n || image[i][j] != oc || image[i][j] == color {
   return
  }
  image[i][j] = color
  for k := 0; k < 4; k++ {
   dfs(i+dirs[k], j+dirs[k+1])
  }
 }
 dfs(sr, sc)
 return image
}

راه حل دوم:

این سؤال یک تصویر را نشان می‌دهد که توسط یک آرایه دوبعدی نشان‌داده‌شده است به رنگ‌های جدید در واقع مسئله یافتن همان فاصله زمانی است که با استفاده از BFS یا DFS قابل‌انجام است. بیایید ابتدا به راه‌حل BFS برای کمک استفاده کنید ابتدا نقطه داده شده را در صف قرار دهید، سپس یک حلقه while انجام دهید، به شرطی که صف خالی نباشد و سپس روشی مشابه پیمایش ترتیب لایه‌ها را انجام دهید. اولین عنصر صف، و قرار داده شده به آن یک‌رنگ جدید اختصاص داده است، و سپس از چهار نقطه اطراف عبور می‌کند، اگر از مرز عبور نمی‌کند و رنگ اطراف همان رنگ شروع، موقعیت به صف اضافه می‌شود. کد زیر را ببینید:

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
 if image[sr][sc] == color {
  return image
 }
 oc := image[sr][sc]
 q := [][]int{[]int{sr, sc}}
 image[sr][sc] = color
 dirs := []int{-1, 0, 1, 0, -1}
 for len(q) > 0 {
  p := q[0]
  q = q[1:]
  for k := 0; k < 4; k++ {
   x, y := p[0]+dirs[k], p[1]+dirs[k+1]
   if x >= 0 && x < len(image) && y >= 0 && y < len(image[0]) && image[x][y] == oc {
    q = append(q, []int{x, y})
    image[x][y] = color
   }
  }
 }
 return image
}