Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大水题,8144K 47ms

Posted by KatrineYang at 2016-08-01 16:58:36 on Problem 1096 and last updated at 2016-08-01 17:01:08
思路很简单!就是先在外面包一层,然后从包好的大长方体的顶点(比如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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator