問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1111思路:
其實(shí)，這是一道簡(jiǎn)單題，關(guān)鍵是要看透如何求周長(zhǎng): 連通塊每格四個(gè)方向（上下左右）如果不在連通塊內(nèi)（超出范圍或者Empty）則周長(zhǎng)加一
DFS或者BFS都可以解決
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 21
5 #define is_valid(x,y) (x>=0 && x<row && y>=0 && y<col)
6 const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
7 const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
8 struct Point {
9 int x, y;
10 }queue[MAX_LEN*MAX_LEN];
11 char grid[MAX_LEN][MAX_LEN];
12 int visited[MAX_LEN][MAX_LEN];
13 int row, col, start_x, start_y;
14 int rt;
15
16 void
17 calculate(int x, int y)
18 {
19 int i, tmpx, tmpy;
20 for(i=0; i<4; i++) {
21 tmpx = x + dx[i];
22 tmpy = y + dy[i];
23 if(!is_valid(tmpx, tmpy) || grid[tmpx][tmpy]=='.')
24 ++rt;
25 }
26 }
27
28 void
29 bfs()
30 {
31 int i, head, tail, nxt_x, nxt_y;
32 head = -1;
33 tail = 0;
34 queue[tail].x = start_x-1;
35 queue[tail].y = start_y-1;
36 visited[start_x-1][start_y-1] = 1;
37 while(head < tail) {
38 ++head;
39 calculate(queue[head].x, queue[head].y);
40 for(i=0; i<8; i++) {
41 nxt_x = queue[head].x + dx[i];
42 nxt_y = queue[head].y + dy[i];
43 if(is_valid(nxt_x, nxt_y) && !visited[nxt_x][nxt_y] && grid[nxt_x][nxt_y]=='X') {
44 ++tail;
45 queue[tail].x = nxt_x;
46 queue[tail].y = nxt_y;
47 visited[nxt_x][nxt_y] = 1;
48 }
49 }
50 }
51 }
52
53 int
54 main(int argc, char **argv)
55 {
56 int i;
57 while(scanf("%d %d %d %d", &row, &col, &start_x, &start_y) != EOF) {
58 if(row==0 && col==0)
59 break;
60 for(i=0; i<row; i++)
61 scanf("%s", grid[i]);
62 rt = 0;
63 memset(visited, 0, sizeof(visited));
64 bfs();
65 printf("%d\n", rt);
66 }
67 }