floodfill算法--Space Station Shielding（空间站屏蔽）_3dslicer floodfill算法

floodfill算法–Space Station Shielding（空间站屏蔽）

题目描述

描述

罗杰·威尔科负责火星低轨道空间站的设计。为了简化结构，空间站由一系列气密隔间模块（ACM）组成，这些模块在太空中一次性连接在一起。罗杰担心的一个问题是可能存在于火星高层大气中的（潜在的）致命细菌。由于空间站偶尔会在高层大气中飞行，因此必须在ACM触摸的所有面上使用额外的屏蔽，无论是边对边还是面对面，接头都是密封的，这样细菌就不会偷偷通过。当然，另一个ACM共享的ACM的任何面都不需要屏蔽，从外面无法接触到的面也不需要屏蔽。罗杰可以在每个ACM的所有表面上加上额外的屏蔽，但成本太高了。因此，他想知道需要额外屏蔽的ACM面的确切数量。

输入

输入包含多个问题实例。每个实例都包含一个空间站的规范。我们假设每个空间站都可以适应一个n x m x k的网格（1<=n，m，k<=60），其中每个网格立方体可能包含也可能不包含ACM。我们对网格立方体进行编号0，1，2。。。，kmn-1，如下图所示。每个空间站规范由以下内容组成：第一行包含四个正整数n m k l，其中n、m和k如上所述，l是空间站中ACM的数量。随后是一组指定ACM的l网格位置的线接下来的一组数表示ACM的网格位置。这些行中的每一行都包含10个整数（可能最后一行除外）。每个空间站都是完全连接的（即宇航员可以在不离开空间站的情况下从空间站的一个ACM移动到空间站的任何其他ACM）。n=m=k=l=0的值终止输入。
Output

For each problem instance, you should output one line of the form

The number of faces needing shielding is s.
Sample Input

2 2 1 3
0 1 3
3 3 3 26
0 1 2 3 4 5 6 7 8 9
10 11 12 14 15 16 17 18 19 20
21 22 23 24 25 26
0 0 0 0
Sample Output

The number of faces needing shielding is 14.
The number of faces needing shielding is 54.
*学习floodfill算法时，接触到了这个题，可惜我看了半天没明白是什么意思。可能是英文的缘故吧，网络翻译的也不好。

思路

1.对空间站的网格用数组进行存储，0表示无ACM，1表示有ACM(ACM本文中是指气密隔间模块）。
2.使用广度优先搜索进行暴力遍历。如果该ACM面左边为空，那么就得进行覆盖。（共有上下左右前后四个方向）
3.为了便于处理，我们存储ACM要的位置要在加1（这并没有多大影响，前提数组够大），以ACM位置在（0，0，0）为例，它的前面为空，需要覆盖。只需将它在数组中的位置放在[1][1][1]位置即可，从[0][0][0]开始遍历
4.x坐标，也就是横坐标，a%(mn)%n+1,a对mn取余的最底下的一面，在%n变得第几个位置。
y坐标，a%(m$\ast$n)/n+1，取底下一面，/n就是第几列，看图;
z坐标，a/(m$\ast$n)+1，找到他是竖的那一面;

代码

using namespace std;
int n, m,k, l,ans;
int arr[70][70][70];
int flag[70][70][70];
struct node {
	int x, y, z;
};
void bfs()
{
	ans = 0;
	queue<node>q;
	node now, next;
	now.x = 0;
	now.y = 0;
	now.z = 0;
	q.push(now);
	while (!q.empty())
	{
		next = q.front();
		q.pop();
		if (flag[next.x][next.y][next.z])
			continue;
		flag[next.x][next.y][next.z] = 1;
		if (next.x-1 >= 0)
		{
			if (arr[next.x - 1][next.y][next.z] == 0)
			{
				if (!flag[next.x - 1][next.y][next.z])
				{
					now.x = next.x - 1;
					now.y = next.y;
					now.z = next.z;
					q.push(now);
				}
			}
			else ans++;
		}
		if (next.x <= n)
		{
			if (arr[next.x + 1][next.y][next.z] == 0)
			{
				if (!arr[next.x + 1][next.y][next.z])
				{
					now.x = next.x + 1;
					now.y = next.y;
					now.z = next.z;
					q.push(now);
				}
			}
			else ans++;
		}
		if (next.y - 1 >= 0)
		{
			if (arr[next.x][next.y - 1][next.z] == 0)
			{
				if (!flag[next.x][next.y - 1][next.z])
				{
					now.x = next.x;
					now.y = next.y - 1;
					now.z = next.z;
				}
			}
			else
				ans++;
		}
		if (next.y <= m)
		{
			if (arr[next.x][next.y + 1][next.z] == 0)
			{
				if (!flag[next.x][next.y + 1][next.z])
				{
					now.x = next.x;
					now.y = next.y + 1;
					now.z = next.z;
					q.push(now);
				}
			}
			else ans++;
		}
		 
		if (next.z - 1 >= 0)
		{
			if (arr[next.x][next.y][next.z - 1] == 0)
			{
				if (!flag[next.x][next.y][next.z - 1])
				{
					now.x = next.x;
					now.y = next.y;
					now.z = next.z - 1;
					q.push(now);
				}
			}
			else ans++;
		}
		if (next.z <= k)
		{
			if (arr[next.x][next.y][next.z + 1] == 0)
			{
				if (!flag[next.x][next.y][next.z + 1])
				{
					now.x = next.x;
					now.y = next.y;
					now.z = next.z + 1;
					q.push(now);
				}
			}
			else ans++;
		}
		
	}

}
int main()
{
	while (cin >> n >> m >>k >> l)
	{
		if (n == 0 && m == 0 && k == 0 && l == 0)
			break;
		memset(arr, 0, sizeof(arr));
		memset(flag, 0, sizeof(flag));
		for (int i = 0; i < l; i++)
		{
			int a;
			cin >> a;
			arr[a % (m * n) % n + 1][a % (m * n) / n + 1][a / (m * n) + 1] = 1;
		}
		bfs();
		cout << ans << endl;
	}
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133