Problem 572 Oil Deposits，石油區塊

此題我利用遞迴解決問題，似乎還有很多種方法，不過我都不太了解就是了，因為我還太嫩 '^^a。

讀入一地區的狀態，字元 '*' 代表沒油，字元 '@' 代表有油。只要是 @ 兩兩相鄰的區域就代表同一區塊，題目就是問你說在這一地區之中，有幾個石油區塊。

寫一可以找出同一石油區塊的函式，找到之後將所有字元便成 '*'：

#define SIZE 102

int m, n;
char Oil[SIZE][SIZE];
void visit(char Oil[][SIZE], int i, int j)
{
    Oil[i][j] = '*';
    int left = (j - 1 >= 0), right = (j + 1 < n), 
        up = (i - 1 >= 0), down = (i + 1 < m); 
        
    if (left && Oil[i][j - 1] == '@')  /* 左 */
        Oil[i][j - 1] = '*', visit(Oil, i, j - 1);
    if (left && down && Oil[i + 1][j - 1] == '@') /* 左下 */
        Oil[i + 1][j - 1] = '*', visit(Oil, i + 1, j - 1);
    if (down && Oil[i + 1][j] == '@') /* 下 */  
        Oil[i + 1][j] = '*', visit(Oil, i + 1, j);
    if (right && down && Oil[i + 1][j + 1] == '@') /* 右下 */ 
        Oil[i + 1][j + 1] = '*', visit(Oil, i + 1, j + 1);
    if (right && Oil[i][j + 1] == '@') /* 右 */ 
        Oil[i][j + 1] = '*', visit(Oil, i, j + 1);
    if (right && up && Oil[i - 1][j + 1] == '@') /* 右上 */ 
        Oil[i - 1][j + 1] = '*', visit(Oil, i - 1, j + 1);
    if (up && Oil[i - 1][j] == '@') /* 上 */ 
        Oil[i - 1][j] = '*', visit(Oil, i - 1, j);
    if (left && up && Oil[i - 1][j - 1] == '@') /* 左上 */ 
        Oil[i - 1][j - 1] = '*', visit(Oil, i - 1, j - 1);
}

最後，主程式只需要如此呼叫即可：

int pocketNum = 0;  
for (i = 0; i < m; i ++)
    scanf("%s", Oil[i]);
for (i = 0; i < m; i ++)
    for (j = 0; j < n; j ++)
        if (Oil[i][j] == '@')
            pocketNum ++, visit(Oil, i, j);
printf("%d\n", pocketNum);

By David.K

p572題目連結
回ACM題庫目錄
回首頁