[コードテストC+]島の個数

今日の質問

https://www.acmicpc.net/problem/4963

島の数

方法

私は毎日十字を対角線に解くだけのものに初めて触れた.ループビューで使用する演算を追加するだけでいいです.

DFSを使用してグラフを参照します.周囲8室を探索し、範囲内で、シングルパスに沿っています.

私の答え

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 50;
int n, m; // 세로, 가로
int map[MAX][MAX];
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};
// 섬의 개수

void dfs(int x, int y){
    map[y][x] = 0;
    for(int i=0;i<8;i++){
        int moveX = x + dx[i];
        int moveY = y + dy[i];
        if(moveX >= m || moveX <0 || moveY >= n || moveY <0)
            continue;
        if(map[moveY][moveX] == 1)
            dfs(moveX, moveY);
    }
}

int solution(){
    int answer = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(map[i][j] == 1){
                dfs(j, i);
                answer++;
            }
        }
    }
    return answer;
}

別の解釈

#include <cstdio>
#include <cstring>
bool land[55][55];
bool visited[55][55];
int dc[]={1,1,0,-1,-1,-1,0,1};
int dr[]={0,1,1,1,0,-1,-1,-1};
int w,h;
void dfs(int r,int c){
	for(int i=0;i<8;++i){
		int rr=r+dr[i];
		int cc=c+dc[i];
		if(rr<=0 || rr>h || cc<=0 || cc>w) continue; 
		if(land[rr][cc]==true && visited[rr][cc]==false) {
			visited[rr][cc]=true;
			dfs(rr,cc);
		}
	}
}
int main () {
	while(scanf("%d %d",&w,&h),w!=0 || h!=0){
		for(int r=1;r<=h;++r){
			for(int c=1;c<=w;++c){
				scanf("%d",&land[r][c]);
			}
		}
		int cnt=0;
		memset(visited,0,sizeof(visited));
		for(int r=1;r<=h;++r)
			for(int c=1;c<=w;++c){
				if(land[r][c]==0 || visited[r][c]) continue;
				dfs(r,c);
				cnt++;
			}
		printf("%d\n",cnt);
	}
	return 0;
}

学ぶべきところ

DFSを使って同様に解けました.