Problem 11244 Counting Stars，星星 ? 物體 ?

此題利用深度優先搜尋法即可解決問題。重點 C 語言程式碼如下：

struct map
{
    char line[104];
}data[104];


void findStar(int i, int j)
{
    isOne ++;
    data[i].line[j] = '.';
    
    if (i - 1 >= 0 && j - 1 >= 0 && data[i - 1].line[j - 1] == '*')
       findStar(i - 1, j - 1);
    if (j - 1 >= 0 && data[i].line[j - 1] == '*')
       findStar(i, j - 1);
    if (i + 1 < r && j - 1 >= 0 && data[i + 1].line[j - 1] == '*')
       findStar(i + 1, j - 1);
       
    if (i - 1 >= 0 && data[i - 1].line[j] == '*')
       findStar(i - 1, j);
    if (i + 1 < r && data[i + 1].line[j] == '*')
       findStar(i + 1, j);    
       
    if (i - 1 >= 0 && j + 1 < c && data[i - 1].line[j + 1] == '*')
       findStar(i - 1, j + 1);    
    if (j + 1 < c && data[i].line[j + 1] == '*')
       findStar(i, j + 1);    
    if (i + 1 < r && j + 1 < c && data[i + 1].line[j + 1] == '*')
       findStar(i + 1, j + 1);
}

而主程式內需如此呼叫：

for (i = 0; i < r; i ++)
{
    for (j = 0; j < c; j ++)
    {
        isOne = 0;
        if (data[i].line[j] == '*') findStar(i, j);
        if (isOne == 1) count ++;
    }
}

打完收假。
By David.K

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