PAT甲級1091

1091. Acute Stroke (30)

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

One important factor to identify acute stroke (急性腦卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M by N matrix, and the maximum resolution is 1286 by 128); L (<=60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).

Then L slices are given. Each slice is represented by an M by N matrix of 0's and 1's, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1's to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are "connected" and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.

Figure 1

Output Specification:

For each case, output in a line the total volume of the stroke core.

Sample Input:

3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0      

Sample Output:

26

/*
#include<cstdio>
const int maxM = 1286, maxN = 128, maxL = 60;
bool inq[maxM][maxN][maxL] = { false };
int brain[maxM][maxN][maxL];
int m, n, l,t;
int countv = 0,volume=0;
bool valid(int x,int y,int z)
{
if (x < 0 || y < 0 || z < 0 || x >= m || y >= n || z >= l)
return false;
if (!brain[x][y][z] || inq[x][y][z])return false;
return true;
}//判斷該點是否有效或未被通路
void DFS(int x, int y, int z)
{
if (valid(x, y, z))
{
inq[x][y][z] = true;
countv++;
}
else
return;
DFS(x, y, z + 1);
DFS(x, y, z - 1);
DFS(x, y-1, z);
DFS(x, y+1, z);
DFS(x-1, y, z);
DFS(x+1, y, z);
}//深度優先周遊
int main()
{
scanf("%d%d%d%d", &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++)
{
scanf("%d", &brain[j][k][i]);
}
}
}
for (int i = 0; i < l; i++)
{
for (int j = 0; j < m; j++)
{
for (int k = 0; k < n; k++)
{
countv = 0;
if (brain[j][k][i]==1&&inq[j][k][i]==false)
{
DFS(j, k, i);
if (countv >= t)//超過其門檻值就加到容量中去
volume += countv;
}
}
}
}
printf("%d", volume);
return 0;
}
遞歸版DFS解法會導緻最後兩個點過不了*/
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
  int x, y, z;//位置(x,y,z)
}Node;
int n, m, slice, T;//矩陣為n*m,共有slice層，T為卒中核心區中1的個數的下限
int pixel[1290][130][61];//三維01矩陣
bool inq[1290][130][61] = { false };//記錄位置(x,y,z)是否已入過隊
int X[6] = { 0,0,0,0,1,-1 };//增量矩陣
int Y[6] = { 0,0,1,-1,0,0 };
int Z[6] = { 1,-1,0,0,0,0 };

bool judge(int x, int y, int z)//判斷坐标(x,y,z)是否需要通路
{
  //越界傳回false
  if (x >= n || x < 0 || y >= m || y < 0 || z >= slice || z < 0)return false;
  //目前位置為0或(x,y,z)已入過隊，則傳回false
  if (pixel[x][y][z] == 0 || inq[x][y][z] == true) return false;
  //以上都不滿足，傳回true
  return true;
}
//BFS函數通路位置(x,y,z)所在的塊，将該塊中所有的“1”的ing都設定為true
int BFS(int x, int y, int z)
{
  int tot = 0;//計數目前塊中1的個數
  queue<node> Q;//定義隊列
  Node.x = x, Node.y = y, Node.z = z;//結點Node的位置為(x,y,z)
  Q.push(Node);//将結點Node入隊
  inq[x][y][z] = true;//設定位置(x,y,z)已入過隊
  while (!Q.empty())
  {
    node top = Q.front();//取出隊首元素
    Q.pop();//隊首元素出隊
    tot++;//目前塊中1的個數加1
    for (int i = 0; i < 6; i++)//循環6次，得到6個增量方向
    {
      int newX = top.x + X[i];
      int newY = top.y + Y[i];
      int newZ = top.z + Z[i];
      if (judge(newX, newY, newZ))//新位置(newX,newY,newZ)需要通路
      {//設定Node的坐标
        Node.x = newX, Node.y = newY, Node.z = newZ;
        Q.push(Node);//将結點Node入隊
        inq[newX][newY][newZ] = true;//設定(newX,newY,newZ)已入過隊
      }
    }
  }
  if (tot >= T)return tot;//如果超過門檻值，則傳回
  else return 0;//否則不記錄該塊1的個數
}
int main()
{
  scanf("%d%d%d%d", &n, &m, &slice, &T);
  for (int z = 0; z < slice; z++)
  {
    for (int x = 0; x < n; x++)
    {
      for (int y = 0; y < m; y++)
      {
        scanf("%d", &pixel[x][y][z]);
      }
    }
  }
  int ans = 0;//記錄卒中核心區中1的個數總和
  for (int z = 0; z < slice; z++)
  {
    for (int x = 0; x < n; x++)
    {
      for (int y = 0; y < m; y++)
      {
        //如果目前位置為1，且未被通路，則BFS目前塊
        if (pixel[x][y][z] == 1 && inq[x][y][z] == false)
        {
          ans += BFS(x, y, z);
        }
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}