时间戳

首页 > 技术文章 > 1002: 当不成勇者的Water只好去下棋了---课程作业---图的填色

1002: 当不成勇者的Water只好去下棋了---课程作业---图的填色

xiezhw3 2013-12-03 17:33 原文

1002: 当不成勇者的Water只好去下棋了

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

由于魔王BOSS躲起来了，说好要当勇者的Water只好去下棋了，他很厉害，基本每局必输。

Water总是不知道为什么把自己的棋下得东一块西一块，而块与块之间总是被对手的棋隔开。概率统计挂了的Water一直没搞清楚到底自己被别人分成了多少块，又来找你帮忙。  
假定Water的棋为X，对手的棋为O。 
给出一个矩阵棋盘，上面布满了棋子，求Water的棋子究竟被对手分成了多少块？

（为了和谐，我们还是用0011代表OOXX）

Input

第一行为n, m。 (0 < n,m <= 100)
接下来 n 行 m 列为01矩阵。
1 为Water的棋。

Output

每组数据输出一行，表示块数。

Sample Input

2 2
01
10
2 3
101
011

Sample Output

2
2

这道题利用的原理是图的填色，从一个二维数组第一个元素开始进行遍历，如果发现一个元素a是有效的，那么久在他的周围找同样有效的元素b，如果找到了，那么就在元素b的周围继续寻找。很明显，这可以用递归来实现。当然你也可以用栈来模拟递归实现。

下面来看看伪代码：

 

 1 4 6
 2 010200
 3 111030
 4 110030
 5 100033
 6 
 7 /* Floodfill  */
 8 bool validNode(newnode) {
 9         cond1 = inMatrix();//是否在图内部
10         cond2 = isFreeNode();//是否是有效元素（这里指值为1）&&是否已经是某个块的成员
11         return cond1 && cond2;
12 }
13 
14 void floodfill(node) {
15     if node是有效元素 {
16         if node还不是某块的成员
17             c[node.x][node.y] = color;
18         
19         //遍历上下左右四个元素
20         for (direction dir) {
21                 newnode = extend(node, dir);
22                 if (validNode(newnode))
23                         floodfill(newnode);
24         }
25     } 
26 }
27 
28 char g[n][m];//储存元素的数组
29 
30 int color = 0;//分块的标志
31 
32 int c[n][m];//分块记录
33 
34 init();//初始化
35 
36 readGraph();//读取分块记录
37 
38 //遍历全部元素，进行分块
39 for (i = 0...n)
40   for (j = 0...m) {
41   // c[i][j] == 0 && g[i][j] == '1'
42         node = freeNode(); 
43         color++;
44         floodfill(node);
45   }

 

然后递归的代码实现如下：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <set>
 4 
 5 using namespace std;
 6 
 7 struct Node{
 8     int x;
 9     int y;
10     Node(int x_ = 0, int y_ = 0) {
11         x = x_;
12         y = y_;
13     }
14 };
15 
16 //上下左右四个节点
17 int borderUponX[4] = {0, 0, 1, -1};
18 int borderUponY[4] = {1, -1, 0, 0};
19 int n, m;
20 char g[101][101];
21 int color = 0;
22 int c[101][101];
23 
24 bool validNode(Node newnode) {
25     if (newnode.x < 0 || newnode.x > n || newnode.y < 0 || newnode.y > m)
26         return false;
27     if (g[newnode.x][newnode.y] != '1' || c[newnode.x][newnode.y] != -1)
28         return false;
29     return true;
30 }
31 
32 void floodfill(Node node) {
33     if(g[node.x][node.y] == '1') {
34         if (c[node.x][node.y] == -1)
35        c[node.x][node.y] = color;
36 
37        for (int i = 0; i != 4; i++) {
38             int pathX = node.x + borderUponX[i];
39             int pathY = node.y + borderUponY[i];
40             Node t = Node(pathX, pathY);
41             if (validNode(t)) {
42                 floodfill(t);
43             }
44         }
45     }
46 }
47 
48 void init() {
49     for (int i = 0; i != n; i++) {
50         scanf("%s", g[i]);
51     }
52     for (int i = 0; i != n; i++)
53         for (int j = 0; j != m; j++)
54             c[i][j] = -1;
55 }
56 
57 void readGraph() {
58     set<int> count;
59     for (int i = 0; i != n; i++) {
60         for (int j = 0;j != m; j++) {
61             if (c[i][j] != -1 && g[i][j] != '0') {
62                 count.insert(c[i][j]);
63             }
64         }
65     }
66     printf("%d\n", count.size());
67 }
68 
69 int main() {
70     while (scanf("%d%d", &n, &m) != EOF) {
71         init();
72 
73         for (int i = 0; i != n; i++) {
74             for (int j = 0;j != m; j++) {
75                 color++;
76                 floodfill(Node(i, j));
77             }
78         }
79         readGraph();
80     }
81     
82     return 0;
83 }

 

 

推荐阅读