題目
給定 n×m 矩陣,由 0 和 1 組成。1 代表是島嶼,0 代表是水,請算出總共有幾個島嶼。(連在一起的 1 是一個島嶼)
輸入:
5 4
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
輸出:3
想法
從左上角[0][0]開始,如果遇到1,而且這個位置沒有走訪過,就把這個位置丟進dfs()裡,等dfs()跑完之後,答案(島嶼數)+1。
dfs(int i, int j): 把傳進來的這個i,j位置,標示為已經走過,然後看這個位置的上下左右是否也是1,如果那個位置是1且沒有超出邊界的話,就把那個位置也丟進dfs()裡。
Code
#include <iostream>
using namespace std;
int n, m;
const int MAX = 300;
int grid[MAX][MAX];
int visited[MAX][MAX];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int i, int j){
visited[i][j] = true;
for(int d=0; d<4; d++){
int nx = i+dx[d];
int ny = j+dy[d];
if(grid[nx][ny]==1 && !visited[nx][ny] && nx>=0 && nx<n && ny>=0 && ny<m){
dfs(nx, ny);
}
}
}
int main(){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> grid[i][j];
}
}
int ans = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j]==1 && !visited[i][j]){
dfs(i, j);
ans++;
}
}
}
cout << ans << '\n';
}