public class Solution {
//用来保存结果
public int[][] res;
//用来计算1的个数
public int sum = 0;
//写到结果中
void writeRes(int[][] res){
for(int i=0;i<res.length;i++){
for(int j=0;j<res[i].length;j++){
if(res[i][j]==1)
res[i][j] = sum;
}
}
}
//深度优先
void dfs(int[][] m,int i,int j){
if(i<0 || i>=m.length || j<0 || j>=m[0].length)
return;
if(m[i][j] == 0)
return;
sum++;
//如果为1 就把它变成0,直到把所有的岛屿都给沉没掉
m[i][j] = 0;
res[i][j] = 1;
dfs(m,i+1,j);
dfs(m,i,j+1);
dfs(m,i,j-1);
}
public int[][] solute(int[][] m){
res = new int[m.length][m[0].length];
for(int i=0;i<m.length;i++){
for(int j=0;j<m[i].length;j++){
sum=0;
dfs(m,i,j);
if(sum > 0)
writeRes(res);
}
}
for(int i=0;i<m.length;i++){
for(int j=0;j<m[i].length;j++){
System.out.print(res[i][j] + " ");
}
System.out.print('\n');
}
return res;
}
public static void main(String[] args) {
int[][] m = {
{0,0,1,1},
{1,1,1,1},
{0,0,1,0}
};
new Solution().solute(m);
}
}
岛屿问题
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 问题 输入是以1和0表示的一张地图,其中1代表陆地,0代表海洋。岛屿是1上下左右相连通的区域。(不包括对角线)输出...
- I found myself not as enthusiastic as before. 这里使用岛屿下沉的思路...