的Java發現多維「污點」 - 遞歸

在多維板（M×N個），其中他的元素的每個人都可以是空或滿。

「污點」大小是彼此相鄰且具有值「x」的元素的數量。

例如這是一個多維陣列（數字是行/列數）

| 0 | 1 | 2 | 3 | 4 | 
0 | | x | | | x | 
1 | x | | | x | x | 
2 | | | x | x | | 
3 | x | | | | | 
4 | x | x | x | | |

有3種污漬

行（0,1），（1,0）（0,4），（1,3），（1,4），（2,2），（2,3） - 大小5
行（3,0），（4,0），（4,1），（4,2） - 尺寸4

我們需要寫誰擁有的簽名遞歸方法：

public static int stain (char [][] mat, int row, int col)

該方法將得到一個行和列，並從那個地方計算色斑的大小，如果沒有污物就會返回0.

我試圖寫出解決方法，但看起來像我這樣做有點麻煩......你能指導我正確的方向嗎？我不是在尋找直接的答案。

謝謝。

幾句話：

可以更改排列，以解決這個問題。

您可以使用重載

你不能使用循環在所有

你不能使用靜態變量

我的代碼：

function stain (char[][] mat, int row, int col) 
{ 
    int col_len = mat.length; 
    int row_len = mat[0].length; 
    if (row < 0 || col < 0 || row >= row_len || col >= col_len) 
     return 0; 

    if (mat[row][col] != 'x') 
     return 0; 

    mat[row][col] = 'y'; 

    // Count current 
    int count = 1; 
    // Go Left 
    count += stain (mat, row, col-1); 
    // Go Right 
    count += stain (mat, row, col+1); 
    // Go Up 
    count += stain (mat, row+1, col); 
    // Go Down 
    count += stain (mat, row-1, col); 

    // Go UpperRight 
    count += stain (mat, row+1, col+1); 
    // Go UpperLeft 
    count += stain (mat, row-1, col+1); 

    // Go DownRight 
    count += stain (mat, row+1, col-1); 
    // Go DownLeft 
    count += stain (mat, row-1, col-1); 

    return count; 
}

來源

2013-12-16 DanR

它應該工作我只是相信這可能是一個更好的解決方法。 – DanR

我有一種感覺，它不會正確地計數污漬的大小（我懷疑它過度計數）或報告所有污漬（它不會記錄個別污漬）。無論如何，「代碼審查交換」（http://codereview.stackexchange.com/）都是「工作代碼」。 SO通常更適合於識別*不起作用的代碼。 – user2864740

這可能更適合codereview.stackexchange。 – Sinkingpoint

你不能使用循環在所有

不幸的是，既然是這樣，你就不會比現在好得多。通過所有鄰居遞歸的代碼可以簡化爲以下，這使的限制精神，儘管違反這些：

for (int dx = -1; dx <= 1; dx++) { 
    for (int dy = -1; dy <= 1; dy++) { 
     // This calls the function on the middle cell again. That's fine. 
     count += stain(mat, row + dx, col + dy); 
    } 
}

因爲你不能使用循環，不過，你真的需要明確的遞歸8次數略有不同的參數。這很容易出錯並且很痛苦，但是很好。

來源

2013-12-17 01:14:39 user2357112

的Java發現多維「污點」 - 遞歸

回答

相關問題