| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大水题,8144K 47ms思路很简单!就是先在外面包一层,然后从包好的大长方体的顶点(比如0,0,0)开始搜索,dfs和bfs应该都可以,我用的dfs懒得手写队列了,stl怕超时
#include <iostream>
#include <stdio.h>
using namespace std;
bool oc[70][70][70];
int cnt = 0;
int N, M, K;
void init(){
for(int i = 0; i < 70; i++)
for(int j = 0; j < 70; j++)
for(int k = 0; k < 70; k++)
oc[i][j][k] = 0;
cnt = 0;
}
void dfs(int x, int y, int z, bool visited[70][70][70]){
visited[x][y][z] = 1;
if(x > 0){
if(oc[x-1][y][z]) cnt++;
else if(!visited[x-1][y][z]){
dfs(x-1, y, z, visited);
}
}
if(x <= N){
if(oc[x+1][y][z]) cnt++;
else if(!visited[x+1][y][z]){
dfs(x+1, y, z, visited);
}
}
if(y > 0){
if(oc[x][y-1][z]) cnt++;
else if(!visited[x][y-1][z]){
dfs(x, y-1, z, visited);
}
}
if(y <= M){
if(oc[x][y+1][z]) cnt++;
else if(!visited[x][y+1][z]){
dfs(x, y+1, z, visited);
}
}
if(z > 0){
if(oc[x][y][z-1]) cnt++;
else if(!visited[x][y][z-1]){
dfs(x, y, z-1, visited);
}
}
if(z <= K){
if(oc[x][y][z+1]) cnt++;
else if(!visited[x][y][z+1]){
dfs(x, y, z+1, visited);
}
}
}
int main() {
while(1){
init();
int gs;
scanf("%d%d%d%d", &N, &M, &K, &gs);
if(N == 0) break;
int temp;
for(int i = 0; i < gs; i++){
scanf("%d", &temp);
oc[temp%N+1][(temp/N)%M+1][temp/(N*M)+1] = 1;
}
bool visited[70][70][70] = {0};
dfs(0,0,0,visited);
printf("The number of faces needing shielding is %d.\n", cnt);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator