推 digua: 大師 04/20 19:58
推 oinishere: 大師 04/20 19:59
→ DJYOSHITAKA: 別捲了 04/20 20:02
推 JIWP: 別卷了 04/20 20:04
※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 1992. Find All Groups of Farmland
: 有一塊m*n的土地
: 1代表農地、0代表森林
: 且農地根森林一定是矩形
: 請找出所有農地的左上座標和右上座標
: 思路 :
: 農地右下的座標其x、y一定是整塊農地裡最大的值
: 從上到下、從左到右去遍歷整塊土地
: 當遇到1就進到dfs函式
: dfs函式裡面就是把land[i][j]變成0
: 並且不斷找最大的x,y
: 這樣就可以找到答案了
: 然後不用4個方向都去找
: 只要找右邊、下面就可以遍歷完整個農地了
: golang code:
: var r, c int
: func findFarmland(land [][]int) [][]int {
: r = len(land)
: c = len(land[0])
: ans := make([][]int, 0)
: for i := 0; i < r; i++ {
: for j := 0; j < c; j++ {
: if land[i][j] == 1 {
: temp := []int{i, j, 0, 0}
: find(&land, i, j, &temp)
: ans = append(ans, temp)
: }
: }
: }
: return ans
: }
: func find(land *[][]int, i, j int, temp *[]int) {
: if i < r && j < c && (*land)[i][j] == 1 {
: (*land)[i][j] = 0
: (*temp)[2] = max((*temp)[2], i)
: (*temp)[3] = max((*temp)[3], j)
: find(land, i, j+1, temp)
: find(land, i+1, j, temp)
: }
: }
思路:
遍歷整個list 遇到1就dfs 因為右下角必然是整個矩形的最大值
用max()找到最大值就可以得到答案
Python Code:
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
def dfs(x,y):
dx = [1,0]
dy = [0,1]
for i in range(2):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x>=0 and new_x<m and new_y>=0 and new_y<n and
land[new_y][new_x] == 1:
land[new_y][new_x] = 0
result[-1][2] = max(result[-1][2],new_y)
result[-1][3] = max(result[-1][3],new_x)
dfs(new_x,new_y)
result = []
n,m = len(land),len(land[0])
for i in range(n):
for j in range(m):
if land[i][j] == 1:
result.append([i,j,i,j])
land[i][j] = 0
dfs(j,i)
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.148 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713614283.A.02B.html