首页 > 代码库 > 1091. Acute Stroke
1091. Acute Stroke
原题链接:http://www.patest.cn/contests/pat-a-practise/1091
本题的前4个case容易过,最后两个case有些难度。如果单纯递归,递归层次会很高从而导致栈溢出,若手动模拟栈实现,又会超出内存限额,于是考虑每次只遍历可连接的节点的个数不超过临界值t。如果节点块连接值达到t,则对这些有效节点进行标记,否则看它们有没有有效的邻节点,若有的话也认为其为有效节点,否则认为其无效。可AC代码如下:
#include <iostream> #include <vector> using namespace std; int m,n,l,t; char matrix[61][1287][129]; bool visited[61][1287][129]; bool isvalid[61][1287][129]; bool getvalid(int x, int y, int z) //得到当前节点有效性记录 { if(x<0 || x>=l || y<0 || y>=m || z<0 || z>=n) { return false; } return isvalid[x][y][z]; } bool getsidevalid(int x, int y, int z) //得到当前节点邻节点有效性逻辑结果 { if(x<0 || x>=l || y<0 || y>=m || z<0 || z>=n) { return false; } return getvalid(x-1,y,z) || getvalid(x+1,y,z) || getvalid(x,y-1,z) || getvalid(x,y+1,z) || getvalid(x,y,z-1) || getvalid(x,y,z+1); } int getval(int x, int y, int z) //若当前节点是否为未访问的‘1’节点,返回记录值1 { if(x<0 || x>=l || y<0 || y>=m || z<0 || z>=n || visited[x][y][z] || matrix[x][y][z] == '0') { return 0; } visited[x][y][z] = true; return 1; } int calvolume(int x, int y, int z) //以当前节点为起始节点,遍历与其相连的节点和它构成的块,块的大小不超过t { if(x<0 || x>=l || y<0 || y>=m || z<0 || z>=n || visited[x][y][z] || matrix[x][y][z] == '0' || getval(x,y,z) != 1) { return 0; } if(getsidevalid(x,y,z)) { isvalid[x][y][z] = true; return 1; } int volume = 1, ptr = 0; bool forbidadd = false; vector<int> xvec,yvec,zvec;//记录块中节点的数组 xvec.push_back(x);//添加起始节点 yvec.push_back(y); zvec.push_back(z); while(xvec.size()>0) { bool allvalid = false; if(!forbidadd) { int xt,yt,zt; for(int i = 0; i < 3; i++) for(int j = -1; j <= 1; j+=2) //添加ptr所指vector中记录节点邻节点 { xt = xvec[ptr]; yt = yvec[ptr]; zt = zvec[ptr]; if(i == 0)xt += j; if(i == 1)yt += j; if(i == 2)zt += j; if(getval(xt,yt,zt) == 1) { xvec.push_back(xt); yvec.push_back(yt); zvec.push_back(zt); volume++; if(getsidevalid(xt,yt,zt)) //若其邻节点有有效邻居,则认为当前节点块有效 { allvalid = true; } } } } ptr++; if(allvalid || xvec.size() >= t) //若已判断定当前块有效,或节点块节点数量已达t { forbidadd = true; for(int i = 0; i < xvec.size(); i++) { isvalid[xvec[i]][yvec[i]][zvec[i]] = true; } break; } if(ptr == xvec.size()) //若节点块已经遍历完全 { break; } } xvec.clear(); yvec.clear(); zvec.clear(); return volume; } int main() { int num = 0; cin>>m>>n>>l>>t; for(int i = 0; i < l; i++) for(int j = 0; j < m; j++) for(int k = 0; k < n; k++) { cin>>matrix[i][j][k]; } for(int i = 0; i < l; i++) for(int j = 0; j < m; j++) for(int k = 0; k < n; k++) { int count = 0; if(matrix[i][j][k]=='1' && !visited[i][j][k]) { count = calvolume(i,j,k); if(count >= t || isvalid[i][j][k]) num += count; } } cout<<num<<endl; }
1091. Acute Stroke
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。