题意:如果一个格子的相邻四个格子中存在两个格子被标记,且这两个格子有公共点,那么这个格子也被标记。给定初始的标记状态,求最终有多少个格子被标记了

思路: 依次对每个格子进行处理,看它能否”生成“新的被标记点。考虑当前点的四个相邻点,如果能被当前点生成,将它加入标记表,并入队,这样直到队列为空是的标记表就是终态。标记是永久标记,因为如果当前格子的四个相邻点不能在当前时刻由当前点生成,那么即便在以后的时刻可以由当前点生成,也完全可以由其它节点来生成它们,效果是等价的,因此标记是永久的。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#pragma comment(linker, "/STACK:10240000,10240000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
bool map[567][567];
queue<pair<intint> > Q;
int n, m;
 
bool inMap(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
bool chk(int x, int y) {
    return inMap(x, y) && map[x][y];
}
bool chk(int x, int y, int i) {
    return chk(x + (dx[i] == 0), y + (dy[i] == 0)) ||
        chk(x - (dx[i] == 0), y - (dy[i] == 0));
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt""r", stdin);
#endif // ONLINE_JUDGE
    int T, cas = 0, k;
    cin >> T;
    while (T --) {
        cin >> n >> m;
        cin >> k;
        int ans = k;
        memset(map, 0, sizeof(map));
        while (!Q.empty()) Q.pop();
        for (int i = 0; i < k; i ++) {
            int u, v;
            scanf("%d%d", &u, &v);
            u --; v --;
            if (map[u][v]) ans --;
            map[u][v] = true;
            Q.push(make_pair(u, v));
        }
        while (!Q.empty()) {
            pair<intint> H = Q.front(); Q.pop();
            for (int i = 0; i < 4; i ++) {
                int x = H.first + dx[i], y = H.second + dy[i];
                if (inMap(x, y) && !map[x][y]) {
                    if (chk(x, y, i)) {
                        map[x][y] = true;
                        Q.push(make_pair(x, y));
                        ans ++;
                    }
                }
            }
        }
        printf("Case #%d:\n%d\n", ++ cas, ans);
    }
    return 0;
}

最新文章

  1. django之一些feature
  2. C++获取当前目录
  3. Apache2.4权限配置(原创帖-转载请注明出处)
  4. sql server 2000数据库 最近经常出现某进程一直占用资源,阻塞?死锁?
  5. Java多线程系列--“基础篇”06之 线程让步
  6. Git工具:Widows下的使用(提交到Github)
  7. centos7最小版本安装nginx+tomcat+java+mysql运行环境
  8. SQL Server 中的触发器(trigger)
  9. SqlSever基础 detalength函数 字节的个数
  10. Linux合并文件、去除重复行的命令
  11. [Python笔记][第二章Python序列-tuple,dict,set]
  12. 分析java中clone()方法 (转载+修改)
  13. 转:批处理for命令详解
  14. python中的JSON(1)
  15. 【javaweb学习笔记】WEB02_HTML&amp;CSS
  16. Mybatis执行BaseExecutor(二)
  17. 基于innodb_print_all_deadlocks从errorlog中解析MySQL死锁日志
  18. [转]图解Docker容器和镜像
  19. Docker Swarm 配置文件存储
  20. httpd 2.4连接php-fpm

热门文章

  1. CSS 中你应该了解的 BFC
  2. SpringBoot全局异常处理与定制404页面
  3. Git把本地代码推送到远程github仓库
  4. 【题解】P2831 愤怒的小鸟 - 状压dp
  5. Laravel - 上手实现 - 文件上传、保存到 public 目录下
  6. 文本序列化【通用】word2sequence,文本序列字典保存
  7. Go gRPC进阶-gRPC转换HTTP(十)
  8. 高级数据结构---赫(哈)夫曼树及java代码实现
  9. Spring Boot中的测试
  10. CtsVerifier-Bluetooth-LE-SEcure-ClientServer-Test测试pass但是无法选择passbutton