acm 11244 counting stars,星星 ? 物體 ?

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct map
{
char line[104];
}data[104];
void (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 ++;
}
}

打完收假。