Red and Black 빨간색 과 검은색 POJ 1979 깊이 검색 알고리즘

원제
     Red and Black
제목:
   검 은 벽돌 만 걷 고, 붉 은 벽돌 은 걷 지 않 으 며, 기껏해야 얼마나 많은 검 은 벽돌 을 걸 을 수 있 습 니까?
   정사각형 의 타일 로 덮 인 장방형 방 이 있 었 다.모든 타일 의 색깔 은 빨간색 이거 나 검은색 이다.한 남자 가 검 은 타일 위 에 서 있 었 다.그 사람      타일 하나 에서 인접 한 네 개의 타일 중 하나 로 옮 길 수 있다.그러나 그 는 빨 간 타일 위 에서 움 직 이 는 것 을 허락 하지 않 고 검은색 타일 위 에서 만 움 직 이 는 것 을 허락 했다. 
입력
입력 은 여러 데이터 세트 로 구성 되 어 있 습 니 다.데이터 집합의 시작 줄 에는 두 개의 정수 W 와 H 가 포함 되 어 있다.W 와 H 는 각각 x - 와 y - 방향의 타일 수량 이다.W 와 H 는 20 을 넘 지 않 습 니 다. 
 '  .  '      검 은 타일  ' # '     빨 간 타일  '@'    한 남자 가 검은색 타일 위 에 서 있 었 다. 
출력
             그 가 초기 타일 에서 도착 할 수 있 는 타일 의 수량 (초기 위치 포함)
Input
 11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..

Output
6
문제 풀이 방향:
    초기 위치 부터 가 까 운 좌 표를 옮 겨 다 니 며 아웃 되 거나 갈 길이 없 을 때 까지.
#include
#include
using namespace std;
char a[24][24];
int dx[4] = {1,-1,0,0};  //  4    
int dy[4] = {0,0,1,-1};
int w,h;
int sum = 0;
void dfs(int p,int q){
	a[p][q] = '#';   //           
	sum++;
	int nx,ny;
	for(int i = 0;i < 4;i++){
		nx = p + dx[i];
		ny = q + dy[i];
		if(a[nx][ny] == '.' && p >= 0 && q >= 0 && nx < h && ny < w){   //       .         
			dfs(nx,ny);  //       nx,ny        4    
		}
	}
	return ;
}
int main(){
	while(scanf("%d%d",&w,&h) != EOF){
		int n,m;
		if(w == h && w == 0){
			break;
		}
		for(int i = 0;i < h;i++){
			for(int j = 0;j < w;j++){
				cin>>a[i][j];
			}
		}
		for(int i = 0;i < h;i++){
			for(int j = 0;j < w;j++){
				if(a[i][j] == '@'){    //         
					dfs(i, j);
				}
			}
		}
		printf("%d
",sum); sum = 0; } return 0; }

좋은 웹페이지 즐겨찾기