島国アイルランド(DFS)

コード#コード#

function solution(board){  
        let answer = 0,
            n = board.length,
            dx = [-1,-1,0,1,1,1,0,-1],
            dy = [0,1,1,1,0,-1,-1,-1];
    
        function DFS(x, y){
            board[x][y]=0;
            for(let k=0; k<8; k++){
                let nx= x+dx[k],
                    ny= y+dy[k];
                if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]===1){
                    DFS(nx,ny);
                }    
            }
        }
        for(let i=0; i<n; i++){
            for(let l=0; l<n; l++){
                if(board[i][l]===1){
                    answer++;
                    DFS(i,l);
                }
            }
        }
        return answer;

    }
let arr=[[1, 1, 0, 0, 0, 1, 0], 
                [0, 1, 1, 0, 1, 1, 0],
                [0, 1, 0, 0, 0, 0, 0],
                [0, 0, 0, 1, 0, 1, 1],
                [1, 1, 0, 1, 1, 0, 0],
                [1, 0, 0, 0, 1, 0, 0],
                [1, 0, 1, 0, 1, 0, 0]];

console.log(solution(arr));

n/a原理

ではゲート探索板である.

1が見つかったら、上下左右、対角線を結ぶ1をすべて0に変換します.(DFS)

回答

回答++.

2(DFS)
2-1. DFS(x,y)ではboard[x][y]を0に変換する.[注意!この過程をしなければ取締役会の価格は1%しか残っていません.
2-2. 上から時計回りにナビゲートすると、数字のない領域があるかもしれません.
したがって、nx>=0&&nx=0&&ny