[PAT解题报告] Acute Stroke
给定一个脑平面图，其实是一个分层的长方体图，每一层是一个长方形，1表示有问题，0表示没问题。先求有问题的连通分量，如果size大于一个阈值就记入总的有问题的size。最后求总体有问题的size是多少。
关键是规模很大，dfs似乎会堆栈溢出或者超时，所以改用bfs，写起来没有dfs舒服——要自己搞队列。60层，每层是1286 ＊
128的，三个维度不同。可以压入到一个int里，最后一维占8bit，中间那维我占了12bit,其实11bit就够了，我只是觉得后两维占20bit比较整……，所以还是用位运算压入一个int代替存放3个不同的int……
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
int m,n,t;
int a[66][1290][130];
const int dc[] = {-1,1,0,0,0,0};
const int dx[] = {0,0,-1,1,0,0};
const int dy[] = {0,0,0,0,-1,1};
queue<int> q;
int bfs(int c,int x,int y) {
if (a[c][x][y] == 0) {
return 0;
}
a[c][x][y] = 0;
q.push((c << 20) | (x << 8) | y);
int r = 1;
for (;!q.empty(); q.pop()) {
int c = q.front() >> 20;
int x = (q.front() >> 8) & 4095;
int y = q.front() & 255;
for (int i = 0; i < 6; ++i) {
int cc = c + dc[i], xx = x + dx[i], yy = y + dy[i];
if ((cc >= 0) && (cc < t) && (xx >= 0) && (xx < m) && (yy >= 0) && (yy < n) && a[cc][xx][yy]) {
++r;
a[cc][xx][yy] = 0;
q.push((cc << 20) | (xx << 8) | yy);
}
}
}
return r;
}
int main() {
int d;
scanf("%d%d%d%d",&m, &n, &t,&d);
for (int i = 0; i < t; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
scanf("%d",&a[i][j][k]);
}
}
}
int answer = 0;
for (int i = 0; i < t; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
int v = bfs(i, j, k);
if (v >= d) {
answer += v;
}
}
}
}
printf("%d\n",answer);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1091
投递美团等公司10个岗位 >