[hdu5254]BFS
2024-08-31 20:49:41
题意:如果一个格子的相邻四个格子中存在两个格子被标记,且这两个格子有公共点,那么这个格子也被标记。给定初始的标记状态,求最终有多少个格子被标记了
思路: 依次对每个格子进行处理,看它能否”生成“新的被标记点。考虑当前点的四个相邻点,如果能被当前点生成,将它加入标记表,并入队,这样直到队列为空是的标记表就是终态。标记是永久标记,因为如果当前格子的四个相邻点不能在当前时刻由当前点生成,那么即便在以后的时刻可以由当前点生成,也完全可以由其它节点来生成它们,效果是等价的,因此标记是永久的。
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< int , int > > 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< int , int > 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; } |
最新文章
- django之一些feature
- C++获取当前目录
- Apache2.4权限配置(原创帖-转载请注明出处)
- sql server 2000数据库 最近经常出现某进程一直占用资源,阻塞?死锁?
- Java多线程系列--“基础篇”06之 线程让步
- Git工具:Widows下的使用(提交到Github)
- centos7最小版本安装nginx+tomcat+java+mysql运行环境
- SQL Server 中的触发器(trigger)
- SqlSever基础 detalength函数 字节的个数
- Linux合并文件、去除重复行的命令
- [Python笔记][第二章Python序列-tuple,dict,set]
- 分析java中clone()方法 (转载+修改)
- 转:批处理for命令详解
- python中的JSON(1)
- 【javaweb学习笔记】WEB02_HTML&;CSS
- Mybatis执行BaseExecutor(二)
- 基于innodb_print_all_deadlocks从errorlog中解析MySQL死锁日志
- [转]图解Docker容器和镜像
- Docker Swarm 配置文件存储
- httpd 2.4连接php-fpm
热门文章
- CSS 中你应该了解的 BFC
- SpringBoot全局异常处理与定制404页面
- Git把本地代码推送到远程github仓库
- 【题解】P2831 愤怒的小鸟 - 状压dp
- Laravel - 上手实现 - 文件上传、保存到 public 目录下
- 文本序列化【通用】word2sequence,文本序列字典保存
- Go gRPC进阶-gRPC转换HTTP(十)
- 高级数据结构---赫(哈)夫曼树及java代码实现
- Spring Boot中的测试
- CtsVerifier-Bluetooth-LE-SEcure-ClientServer-Test测试pass但是无法选择passbutton