博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BFS 2015百度之星初赛2 HDOJ 5254 棋盘占领
阅读量:6442 次
发布时间:2019-06-23

本文共 2051 字,大约阅读时间需要 6 分钟。

 

1 /*  2     BFS:先把1的入队,每个1和它相邻的组合后看看能不能使0变1,若有则添加入队,change函数返回改变了多少个0  3     注意:结果还要加上原来占领的  4 */  5 #include 
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 using namespace std; 13 14 const int MAXN = 5e2 + 10; 15 const int INF = 0x3f3f3f3f; 16 int a[MAXN][MAXN]; 17 int dx[4] = {-1, -1, 1, 1}; 18 int dy[4] = {-1, 1, -1, 1}; 19 int n, m; 20 queue
> Q; 21 22 int change(int x, int y) 23 { 24 25 int cnt = 0; 26 for (int i=0; i<4; ++i) 27 { 28 int tx = x + dx[i]; int ty = y + dy[i]; 29 if (tx < 1 || tx > n) continue; 30 if (ty < 1 || ty > m) continue; 31 if (a[tx][ty] == 1) 32 { 33 if (i == 0 || i == 2) 34 { 35 if (a[tx][ty+1] == 0) {a[tx][ty+1] = 1; ++cnt; Q.push (make_pair (tx, ty+1));} 36 if (a[x][y-1] == 0) {a[x][y-1] = 1; ++cnt; Q.push (make_pair (x, y-1));} 37 } 38 else if (i == 1 || i == 3) 39 { 40 if (a[tx][ty-1] == 0) {a[tx][ty-1] = 1; ++cnt; Q.push (make_pair (tx, ty-1));} 41 if (a[x][y+1] == 0) {a[x][y+1] = 1; ++cnt; Q.push (make_pair (x, y+1));} 42 } 43 } 44 } 45 46 return cnt; 47 } 48 49 int BFS(void) 50 { 51 int ans = 0; 52 while (!Q.empty ()) 53 { 54 int x = Q.front ().first; int y = Q.front ().second; Q.pop (); 55 ans += change (x, y); 56 } 57 58 return ans; 59 } 60 61 int main(void) //2015百度之星初赛2 HDOJ 5254 棋盘占领 62 { 63 int t, cas = 0; scanf ("%d", &t); 64 while (t--) 65 { 66 while (!Q.empty ()) Q.pop (); 67 scanf ("%d%d", &n, &m); 68 memset (a, 0, sizeof (a)); 69 70 int g; scanf ("%d", &g); 71 int cnt = 0; 72 while (g--) 73 { 74 int x, y; scanf ("%d%d", &x, &y); 75 if (a[x][y] == 0) 76 { 77 cnt++; a[x][y] = 1; Q.push (make_pair (x, y)); 78 } 79 } 80 81 printf ("Case #%d:\n", ++cas); 82 printf ("%d\n", BFS () + cnt); 83 } 84 85 return 0; 86 } 87 88 89 90 91 /* 92 4 93 2 2 94 2 95 1 1 96 2 2 97 3 3 98 3 99 1 1100 2 3101 3 2102 2 4103 5104 1 1105 1 1106 1 2107 1 3108 1 4109 2 4110 2111 1 1112 2 4113 */

 

转载于:https://www.cnblogs.com/Running-Time/p/4544521.html

你可能感兴趣的文章
史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现(Eureka)
查看>>
JS笔记(7): 原型和原型链
查看>>
Springboot
查看>>
Python2.0即将消亡,你该做什么?
查看>>
基于PHP + TRIE树实现敏感词过滤算法
查看>>
仿win8菜单的按下缩小抬起恢复大小的效果
查看>>
att()和prop()的区别
查看>>
官方提示:百度智能小程序免费申请,没有“官方授权”合作
查看>>
redux原理
查看>>
好程序员Web前端面试题Javascript篇汇总
查看>>
Shell基础
查看>>
Java工程师学习指南入门篇
查看>>
Seagate将提供更广泛的14TB型硬盘跨足企业到一般消费者
查看>>
技术分享主干
查看>>
快速配置 webpack 多入口脚手架
查看>>
vue-router 一些容易被忽略的知识点
查看>>
速览新特性--react✈️16.0=>16.6
查看>>
996工作制该取消吗?
查看>>
“六一”儿童节就要到了,赶快为喜欢的ta下场星星雨吧~
查看>>
SpringMVC入门学习---文件上传
查看>>