1091 Acute Stroke 需再做
这是BFS的典型应用场景：求给定矩阵中块(由相邻的点组成)的大小之和。不同的是这一次是三维。
判断是否邻接的依据是是否有公共边，还是可以用上增量数组的技巧
int X[6] = {0,0,1,-1,0,0};//增量数组
int Y[6] = {1,-1,0,0,0,0};
int Z[6] = {0,0,0,0,1,-1};总体思路是，用一个和输入形状完全一样的in queue数组判断每个点是否已经进过队列，以防重复计算。
对输入数组开始遍历，如果一个点既为1又没进过inq，对其进行BFS。
BFS的作用是返回当前区域的大小，注意一开始size的初值设为1而不是0，因为至少有目前这个结点是1，最后返回时如果低于阈值就返回0(这样外层可以直接加上)，如果达到阈值就返回size。
//BFS函数的任务是访问(x,y,z)中的块中的所有节点，返回块的大小
int BFS(int x,int y,int z){int size = 1;//该结点自身 queue<Node> que;//定义队列node.x = x;//赋予当前结点坐标 node.y = y;node.z = z;que.push(node);//起点入队inq[x][y][z] = true;while(!que.empty()){Node top = que.front();//取出队首元素que.pop();//队首元素出队for(int i=0;i<6;i++){int newX = top.x + X[i];int newY = top.y + Y[i];int newZ = top.z + Z[i]; if(judge(newX,newY,newZ)){//判断是否能够入队size ++;//该区域又一次壮大 node.x = newX;node.y = newY;node.z = newZ;que.push(node);//node入队inq[newX][newY][newZ]= true;//设置node已经入队 }}}if(size>=t)return size;else return 0;
}易错点：三层循环的位置错误
应对办法：想想哪些维度在变，哪些不变
AC代码
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>using namespace std;const int maxn = 100;struct Node{int x,y,z;//坐标(x,y,z)
}node;//临时结点int m,n,l;//行和列和层
int t;//区域大小的下限
int brain[1286][128][60];//存放脑切片的情况
bool inq[1286][128][60] = {false};//是否已经入过BFS的队列
int X[6] = {0,0,1,-1,0,0};//增量数组
int Y[6] = {1,-1,0,0,0,0};
int Z[6] = {0,0,0,0,1,-1};//判断当前位置是否能够入队
bool judge(int x,int y,int z){//越界，不行if(x<0||x>=n||y<0||y>=m||z<0||z>=l)return false;//不是1，不行if(!brain[x][y][z])return false; //已经入过了，不行if(inq[x][y][z])return false;return true;
}//BFS函数的任务是访问(x,y,z)中的块中的所有节点，返回块的大小
int BFS(int x,int y,int z){int size = 1;//该结点自身 queue<Node> que;//定义队列node.x = x;//赋予当前结点坐标 node.y = y;node.z = z;que.push(node);//起点入队inq[x][y][z] = true;while(!que.empty()){Node top = que.front();//取出队首元素que.pop();//队首元素出队for(int i=0;i<6;i++){int newX = top.x + X[i];int newY = top.y + Y[i];int newZ = top.z + Z[i]; if(judge(newX,newY,newZ)){//判断是否能够入队size ++;//该区域又一次壮大 node.x = newX;node.y = newY;node.z = newZ;que.push(node);//node入队inq[newX][newY][newZ]= true;//设置node已经入队 }}}if(size>=t)return size;else return 0;
} int main(){scanf("%d%d%d%d",&n,&m,&l,&t);for(int k=0;k<l;k++){for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&brain[i][j][k]);}}}int ans = 0;for(int k=0;k<l;k++){for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(brain[i][j][k]&&!inq[i][j][k]){ans += BFS(i,j,k);}}}}printf("%d\n",ans);return 0;
}相关文章：
Ext UI 第一步
Code//Ext.onReady(function(){ var _panelnew Ext.Panel({ renderTo:Ext.getBody(), title:"XXX" });});空面板 加按钮方法:addButton(String/Object _config,Function _handler,Object _scope):添加一个按钮对象到面板Codevar loadfunction(){ …
深入浅出 Java Concurrency (29): 线程池 part 2 Executor 以及Executors[转]
Java里面线程池的顶级接口是Executor，但是严格意义上讲Executor并不是一个线程池，而只是一个执行线程的工具。真正的线程池接口是ExecutorService。 下面这张图完整描述了线程池的类体系结构。 首先Executor的execute方法只是执行一个Runnable的任务&…
WPF的消息机制（二）- WPF内部的5个窗口之隐藏消息窗口
原文:WPF的消息机制（二）- WPF内部的5个窗口之隐藏消息窗口版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/powertoolsteam/article/details/6109036 目录 WPF的消息机制（一）-让…
二叉树：root==NULL和*root==NULL的区别
root NULL 通常为查找的递归边界，说明当前结点不存在。 *root NULL 表明当且结点存在，但是内容不存在。是创建一棵二叉树时的初始化操作。 前者常用得多。
Intent携带额外的数据的方法
1、putExtras(Bundle data):向Intent中放入需要“携带”的数据。2、putXxx(String key,Xxx data):向Bundle放入Int、Long等各种类型的数据。3、putSerializable(String key,Serializable data):向Bundle中放入一个可序列化的对象。转载于:https://www.cnblogs.com/ahao214/p/41…
为什么 JavaScript 的私有属性使用 # 符号
这几天 JavaScript 的私有属性又成为了前端社区热议的话题。原因很简单，这家伙长这样： 惊不惊喜！意不意外！ 而且 TC39 委员会以及对此达成了一致意见，并且该提案已经进入了 stage 3。在 es 规范阶段 stage 3 是候选提案…
程序员感悟----路该怎么走
有一句话我一直记得很深，“当人深处迷茫之中时早已不再迷茫”。很绕很矛盾的话，也可能有人听到后会马上跳脚喊，我一直迷茫怎么还是迷茫呢？呵呵。静一下想一下再喊。 大家都这么大了，路该怎么走，你知道么&am…
1020 Tree Traversals
1. 有这样一个经典结论：中序序列可以和先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树，而后三者两两搭配或者三个一起上都不行。因为从本质上来说，后三者都只提供根结点，只有通过中序才能区分左右子树。 2. 本题用…
Android添加权限大讲解
http://bbs.51cto.com/thread-1096739-1.html 对于新手来说，最烦恼的不是如何从网上下载到安卓项目，而是下载到的安卓项目不知道如何添加权限和要添加哪些权限。现在就针对安卓的权限来讲解这些权限应该具体用在什么地方 首先在项目下找到 AndroidManife…
经典算法之选择排序
问题 有一数组a，长度为n，把数组中的元素从大到小重新排列 思路 选择排序十分容易理解。可以理解为有一个盘子，里面装着很多钻石，你可以从里面拿钻石，但一次只可以拿一颗。第一次你当然会拿最大的出来了，第二…
PHP 读写数据库出现中文乱码问题
一、我在PHP读写数据库时，出现中文乱码问题的解决方案： 1、加入一句话就行了： mysql_query("set character set utf8");//读库 mysql_query("set names utf8");//写库 //其实读写都可以只加入 m…
1086 Tree Traversals Again
1. 这题的核心部分是，根据二叉树的先序序列和中序序列求后序序列。等于是在1020 Tree Traversals这一题的基础上，把怎么得到先序序列和中序序列的难度加大了，不是直接给出，而是要曲折一点得到。 2. 先序序列的得到就是把Push后面…
Eclipse的Java工作集和多工程构建路径
一、Java工作集： Eclipse有一个小功能，就是创建Java Working Set。它的作用是解决Package Explorer窗格中创建很多工程时出现拥挤的麻烦。 在创建（New对话框）时可以加入原来存在的Java工程。创建完后，在左方Package Ex…
ORA-08002: sequence MySeq.currval is not yet defined in this session
2019独角兽企业重金招聘Python工程师标准>>> MySeq.currval 从你的会话中的MySeq序列获取最新的值并返回，因此，它未曾被定义，直到你在你的会话中至少一次用MySeq.NEXTVAL获取一个值。CURRVAL的目的是让你在你的代码中使用某个序列…
【Vegas原创】exp时，ORA-00932: 数据类型不一致解决方法
现象： EXP-00056: 遇到 ORACLE 错误 932 ORA-00932: 数据类型不一致: 应为 BLOB, CLOB, 但却获得 CHAR EXP-00000: 导出终止失败 解决方法： 运行2个脚本： SQL> ?/rdbms/admin/catmetx.sql SQL> ?/rdbms/admin/utlrp.sql 转载于:htt…
1102 Invert a Binary Tree 需再做
1. 题目的输入是，先给出结点总数N，然后N行给出的是值为x（0<x<N-1）的结点的左右结点的值，若不存在左/右结点，则值为 - 。 2. 这一题我用动态链表没有做出来，根据参考书提示改用静态链表。…
iOS安全攻防(八)Thoes的Logos简介
个人原创，转帖请注明来源:cnblogs.com/jailbreaker 上一篇帖子，讲到使用iOSOpenDev开发基于Theos的Tweak,功能Hook了SpringBoard的 -(void)applicationDidFinishLaunching:(id)application。 先简单讲一下Hook,Hook中文翻译为“钩子”，非常形…
Algs4-1.1.13编写一段代码，打印出一个M行N列的二维数组的转置(交换行和列）
1.1.13编写一段代码，打印出一个M行N列的二维数组的转置(交换行和列）。public class Test{public static void main(String[] args){//初始化int MInteger.parseInt(args[0]);int NInteger.parseInt(args[1]);String[][] arraynew String[M][N];for (int…
1053 Path of Equal Weight
1. 以下两组关系很大的概念 树的深度优先搜索 - 先根遍历 - 递归 树的广度优先搜索 - 层序遍历 - 非递归 本题考察的是前者，我设置了这样一个结构体 struct Prestruct{int totalWei 0;vector<int> pre; };Prestruct pre[maxn]; pre[idx].pre向量存放父节…
MapXtreme 2005 学习心得 在地图上创建点/线并显示标注(五)
新建示例 1：新建项目 新建一个网站，选择MapXtreme 6.7.1 Web Application在App_Code中，我们新建一个类，起名叫:LayerManager.cs2：把上节函数放到类LayerManager中 把上一节的函数代码全copy过来，还有using的…
无人驾驶——对frenet坐标的理解
好的确定车和路之间的关系，我们通常将车辆的在大地坐标坐标转化为车辆和道路之间的frenet坐标。 可能有人会疑问为什么转换后就方便了呢？我们来看一个例子。 在大地坐标下： 无人车首先要知道红色车的位置。通过传感器得到目标在车辆坐标系下的…
1079 Total Sales of Supply Chain
1. 这道题考察的是树的层次遍历，结点需要有层这个属性，对于我来说，难点在于什么时候给层赋值，看书后知道应该是在加入队列之前(不管是根节点还是之后所有节点)。 2. 一开始算得216，原因是把r直接加一当作底数…
在VS下用C语言连接SQLServer2008
在VS下用C语言连接SQLServer2008 原文:在VS下用C语言连接SQLServer2008 step1:启动SQLSERVER服务 step2:打建立数据库test,在test库中建立test表(a varchar(200),b varchar(200)) step3:建立系统DSN,开始菜单 ->运行 ->odbcad32, 添加->SQL SERVER Native Client 1…
canvas.width和canvas.style.width区别以及应用
今天讲的内容是canvas.width和canvas.style.width的区别，在没有做canvas项目之前，其实我是并没有深入了解过这两个属性的，最近在研究canvas项目的自适应问题，尤其是在canvas中置入图片，碰到了图片模糊的问题࿰…
vj p1042捕风捉影 题解
原体叙述 题意就是让你找出m,n之间的既是回文数又是素数的数 此题完全可以打表。除打表外，方法如下： 构成法 根据数学知识可知，如果一个回文数为偶数位，则必然能被11整除。 即所找的结果必为奇数位。 这样，大致方法就出…
1090 Highest Price in Supply Chain 需再做
1. 由于用不上结点的数据域，所以可以只用整型向量数组存放每一个结点的子节点下标即可。 2. 涉及到层次，未必用层次遍历，本题用先根遍历，也就是深度优先代码更优雅。 3. 这题创建树未必难，但是题目有一句话必须读懂e…
有关Adobe公司的PostScript语言授权问题
各位大神好： 最近公司打算用PostScript语言开发一款打印机产品，本人现在正对这方面予以了解，但是关于Postscript却一无所知，请问园子里的大神们有没有知道的。 我是想咨询一下有关adobe公司在上世纪80年代公司刚成立的时候所推出的…
INTERSECT/EXCEPT VS. IN/NOT IN
我真是OLD到死，虽然记得以前肯定看到过INTERSECT/EXCEPT这两个关键字，前不久还在羡慕Oracle有/-集合操作符而SQL Server怎么竟然没有。。。现在想想难怪当初微软面试的时候面试官告诉我最好了解一下SQL Server 2005新的函数。。。 下面翻译一下http://ww…
聊聊storm的stream的分流与合并
序 本文主要研究一下storm的stream的分流与合并 实例 Testpublic void testStreamSplitJoin() throws InvalidTopologyException, AuthorizationException, AlreadyAliveException {TopologyBuilder builder new TopologyBuilder();builder.setSpout("sentence-spout&quo…
1106 Lowest Price in Supply Chain
1. 本题和1090 Highest Price in Supply Chain适成对比，都是先构建一棵树，但本题是求最小层数和个数，链接题是求最大层数和个数。在极值更换和个数更新方面，两道题是一样的，但要注意，如果是求最小ÿ…