[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]
3
[[0]]
0
[[1,1],[1,1]]
1
01矩阵范围<=200*200
public class Solution {
private static final int[][] position = new int[][]{
{-1,0},{1,0},
{0,1},{0,-1}
};
public int solve (char[][] grid) {
int row = grid.length,col = grid[0].length;
boolean[][] used = new boolean[row][col];
int count = 0;
for(int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if(used[i][j] || grid[i][j] == '0') continue;
//dfs(grid, i, j, used);
bfs(grid, i, j, used);
count++;
}
}
return count;
}
private void dfs(char[][] grid, int i, int j, boolean[][] used) {
if (!inArea(grid, i, j) || grid[i][j] == '0' || used[i][j]) {
return;
}
used[i][j] = true;
for (int[] move : position) {
int newRow = i + move[0];
int newCol = j + move[1];
dfs(grid, newRow, newCol, used);
}
}
private void bfs(char[][] grid, int i, int j, boolean[][] used){
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
used[i][j] = true;
while (!queue.isEmpty()){
int[] temp = queue.poll();
int row = temp[0];
int col = temp[1];
for (int[] move : position) {
int newRow = row + move[0];
int newCol = col + move[1];
if (inArea(grid, newRow, newCol) && grid[newRow][newCol] == '1' && !used[newRow][newCol]) {
queue.offer(new int[]{newRow, newCol});
used[newRow][newCol] = true;
}
}
}
}
private boolean inArea(char[][] grid, int i, int j){
return i >= 0 && i < grid.length && j >=0 && j < grid[0].length;
}
} 
import java.util.*;
public class Solution {
// 不想多传值，所以增加的全局变量
int lengthX;
int lengthY;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
int count = 0;
lengthX = grid.length;
lengthY = grid[0].length;
for (int j = 0; j < lengthY; j++) {
for (int i = 0; i < lengthX; i++) {
if (grid[i][j] == '1') {
// 改变为0，表示已经算过了，下次不要再进入
grid[i][j] = '0';
// 向四周递归遍历，只有四周都为0才会返回true，以为之前将自身已经改为0了，所以没有影响
if (findNext(i + 1, j, grid)
&& findNext(i - 1, j, grid)
&& findNext(i, j + 1, grid)
&& findNext(i, j - 1, grid)) {
count++;
}
}
}
}
return count;
}
private boolean findNext(int x, int y, char[][] grid) {
if (x == lengthX || y == lengthY || x < 0 || y < 0) {
return true;
}
if (grid[x][y] == '0') {
return true;
} else {
// 改变为0，表示已经算过了，下次不要再进入
grid[x][y] = '0';
// 向四周递归遍历，只有四周都为0才会返回true，以为之前将自身已经改为0了，所以没有影响
return (findNext(x + 1, y, grid)
&& findNext(x - 1, y, grid)
&& findNext(x, y + 1, grid)
&& findNext(x, y - 1, grid));
}
}
} 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
int count = 0;
int len1 = grid.length;
int len2 = grid[0].length;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (grid[i][j] != '0') {
floodfill(grid, i, j);
count++;
}
}
}
return count;
}
public void floodfill (char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length) return;
if (grid[i][j] == '0') {
return;
} else {
grid[i][j] = '0';
}
floodfill(grid, i + 1, j);
floodfill(grid, i - 1, j);
floodfill(grid, i, j + 1);
floodfill(grid, i, j - 1);
}
} 
import java.util.*;
public class Solution {
//岛屿数量
public int count = 0;
//移动方向，左、右、上、下
public int[][] movement = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 判断岛屿数量
将联通的陆地改为海洋，进循环几次就说明有几个岛屿，dfs
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 0 ; i < m ; ++i) {
for (int j = 0 ; j < n; ++j) {
if (grid[i][j] == '1') {
//深度优先搜索，将所有联通的陆地改为海洋
dfs(grid, i, j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid, int i, int j) {
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length){
//如果越界直接返回
return ;
}
if(grid[i][j] == '0'){
//如果为0说明是海洋，直接返回
return ;
}
//没越界且不是海洋，就是陆地,将陆地改为海洋
grid[i][j] = '0';
for(int k = 0 ; k < 4;++k){
int tempX = i + movement[k][0];
int tempY = j + movement[k][1];
dfs(grid,tempX,tempY);
}
}
} 
public int solve (char[][] grid) {
// 回溯 而不是dp
//1是陆地 0是海洋
int m=grid.length;
int n=grid[0].length;
int ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){//注意这里是char 1,而不是int 1
build(grid,i,j);
ans++;//陆地数量+1
}
}
}
return ans;
}
public void build(char[][] grid,int i,int j){ //判断是不是陆地，不需要返回值
int m=grid.length;
int n=grid[0].length;
//写截至条件
//（这个对网格的控制要放在前面，先把有效范围卡死，再进行其他操作）
if(i<0||j<0||i>=m||j>=n){//把i、j的取值分别控制在0~m-1或0~n-1
return ;
}
if(grid[i][j]!='1'){//可能出现0（海水）、2（被沉没的陆地）
return ;
}
//走到这里，说明当前网格是陆地1，沉没当前陆地变成2
grid[i][j]='2';
//回溯
build(grid,i,j-1);
build(grid,i,j+1);
build(grid,i-1,j);
build(grid,i+1,j);
} public class Solution {
// 向上的向量
private static final int[] UP = {-1, 0};
// 向下的向量
private static final int[] DOWN = {1, 0};
// 向左的向量
private static final int[] LEFT = {0, -1};
// 向右的向量
private static final int[] RIGHT = {0, 1};
// 上下左右的向量
private static final int[][] DIRECTIONS = {UP, DOWN, LEFT, RIGHT};
public int solve (char[][] grid) {
// 计数器
int counter = 0;
int height = grid.length;
int width = grid[0].length;
// 标记走过的路径，不会撤销
boolean[][] visited = new boolean[height][width];
for (int x = 0; x < height; x++) {
for (int y = 0; y < width; y++) {
// 如果这个位置已经被访问过了或者这个位置就是海洋，直接跳过
if (visited[x][y] || grid[x][y] == '0') {
continue;
}
// 这个位置是陆地，扩散
spread(grid, visited, x, y);
// 计数器加1
counter++;
}
}
return counter;
}
private void spread(char[][] grid, boolean[][] visited, int x, int y) {
// 越界直接返回
if (x >= grid.length || x < 0 || y >= grid[x].length || y < 0) {
return;
}
// 如果访问过了或者是海洋，直接返回
if (visited[x][y] || grid[x][y] == '0') {
return;
}
// 标记访问过了
visited[x][y] = true;
// 对x,y这个位置做出上下左右的选择
for (int[] direction : DIRECTIONS) {
int nX = x + direction[0];
int nY = y + direction[1];
spread(grid, visited, nX, nY);
}
}
} 
public class Solution {
public int solve (char[][] grid) {
if (grid.length == 0) {
return 0;
}
int result = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] == '1') {
++result;
dfs(grid, j, i);
}
}
}
return result;
}
public void dfs(char[][] grid, int x, int y) {
int n = grid.length;
int m = grid[0].length;
if (x < 0 || x >= m || y < 0 || y >= n || grid[y][x] == '0') {
return;
}
grid[y][x] = '0';
dfs(grid, x - 1, y);
dfs(grid, x + 1, y);
dfs(grid, x, y - 1);
dfs(grid, x, y + 1);
}
} 
import java.util.*;
public class Solution {
public int solve (char[][] grid) {
//二维数组为空的情况
if(grid==null || grid.length==0){
return 0;
}
//遍历二位数组，得到结果
int res = 0;
int row = grid.length;
int col = grid[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j] == '1'){
res++;
dfs(grid,i,j);
}
}
}
return res;
}
public void dfs(char[][] grid, int x,int y){
int row = grid.length;
int col = grid[0].length;
if(x<0 || y<0 || x>=row || y>=col || grid[x][y]=='0'){
return;
}
grid[x][y] = '0';
dfs(grid,x-1,y);
dfs(grid,x+1,y);
dfs(grid,x,y-1);
dfs(grid,x,y+1);
}
} import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
if(grid==null || grid.length==0){
return 0;
}
int res = 0;
int row = grid.length;
int col = grid[0].length;
Queue<int[]> q = new LinkedList<>();
//队列存放数值为1的下标，出队列后，判断它的上下左右数值是否为1，若为则继续加入队列
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j] == '1'){
res++;
q.add(new int[]{i,j});
grid[i][j] = '0';
while(!q.isEmpty()){
int[] temp = q.poll();
int x = temp[0];
int y = temp[1];
if(x-1>=0 && grid[x-1][y] == '1'){
q.add(new int[]{x-1,y});
grid[x-1][y] = '0';
}
if(x+1<row && grid[x+1][y] == '1'){
q.add(new int[]{x+1,y});
grid[x+1][y] = '0';
}
if(y-1>=0 && grid[x][y-1] == '1'){
q.add(new int[]{x,y-1});
grid[x][y-1] = '0';
}
if(y+1<col && grid[x][y+1] == '1'){
q.add(new int[]{x,y+1});
grid[x][y+1] = '0';
}
}
}
}
}
return res;
}
} 
public int solve (char[][] grid) {
//write code here
int len1 = grid.length;
int len2 = grid[0].length;
int res = 0;
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(grid[i][j] == '1'){
res++;
//dfs方法用于淹没陆地，防止重复计算
dfs(grid,i,j,len1,len2);
}
}
}
return res;
}
public void dfs(char[][] grid,int i,int j,int len1,int len2){
if(i<0 || j<0 || i>=len1 || j>=len2){
return;
}
if(grid[i][j] == '0'){
return;
}
grid[i][j] = '0';
dfs(grid,i+1,j,len1,len2);
dfs(grid,i-1,j,len1,len2);
dfs(grid,i,j+1,len1,len2);
dfs(grid,i,j-1,len1,len2);
} //广度优先 public static int solve(char[][] grid){ int result = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { if (grid[i][j] == '1') { result++; bfs(grid, i, j); } } } return result; }
private static void bfs(char[][] grid, int i, int j) { int[] u; grid[i][j] = '0'; int m = grid.length; int n = grid[i].length; LinkedList<int[]> queue = new LinkedList(); queue.add(new int[]{i, j}); while (!queue.isEmpty()) { u = queue.removeFirst(); if (u[0]-1>=0 && grid[u[0]-1][u[1]] == '1') { grid[u[0]-1][u[1]] = '0'; queue.addLast(new int[]{u[0]-1, u[1]}); } if (u[0]+1<m && grid[u[0]+1][u[1]] == '1') { grid[u[0]+1][u[1]] = '0'; queue.addLast(new int[]{u[0]+1, u[1]}); } if (u[1]-1>=0 && grid[u[0]][u[1]-1] == '1') { grid[u[0]][u[1]-1] = '0'; queue.addLast(new int[]{u[0], u[1]-1}); } if (u[1]+1<n && grid[u[0]][u[1]+1] == '1') { grid[u[0]][u[1]+1] = '0'; queue.addLast(new int[]{u[0], u[1]+1}); } } }
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve(char[][] grid){
// 初始化路径图， false表示没走过，true表示走过
boolean[][] pathMap = initPathMap(grid);
// 返回值总数，统计共有多少岛屿
int count = 0;
// 遍历二维char数组每一个点
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
// 只要路径图上该点为false 没走过，并且当前点是1的时候 ---就dfs搜索和它相关联的点
if(!pathMap[i][j] && grid[i][j] == '1'){
// 返回值是共有多少为1的点与之关联
// 每次dfs方法结束后，从grid[i][j] 开始，所有与之关联的点都在pathMap记录为true了
dfs(grid, pathMap, i, j);
// 查询后将count++ 表示一个岛屿搜索结束了
count++;
}
}
}
// 最终返回count
return count;
}
public void dfs(char[][] grid, boolean[][] pathMap, int line, int col){
// 如果点位等于0 或者 该点位已经走过了，那么返回0
if(grid[line][col] == '0' || pathMap[line][col]) return;
// 将当前点位设置为true，表示已经走过了
pathMap[line][col] = true;
// 只要下一行不越界，就递归到下一行去查看
if(line+1 < grid.length) dfs(grid, pathMap, line + 1, col);
// 只要当前行的下一格不越界，就递归到下一格去查看
if(col + 1 < grid[line].length) dfs(grid, pathMap, line, col + 1);
// 只要上一行不越界，就递归上一行去查看
if(line - 1 >= 0) dfs(grid, pathMap, line - 1, col);
// 只要当前行的上一格不越界，就递归上一格去查看
if(col - 1 >= 0) dfs(grid, pathMap, line, col - 1);
}
public static boolean[][] initPathMap(char[][] grid){
return new boolean[grid.length][grid[0].length];
}
} 
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
private char[][] test;
public int solve (char[][] grid) {
// write code here
//对于每个点，先判断其上下左右是否为1
//如果有一个为1,就返回true,而且要把这些已经遍历过的且为1的改为0
//如果全都是0，就返回false
test = grid;
int count = 0;
for (int i=0;i<grid.length;i++){
for (int j=0;j<grid[0].length;j++){
boolean falg = help(i, j);
if (falg) {
count++;
}
}
}
return count;
}
public boolean help(int i, int j) {
if (i >= test.length || j >= test[0].length) {
return false;
}
if(i<0||j<0){
return false;
}
boolean flag = false;
if (test[i][j] == '1') {
//这里我就判断右下两个节点的内容为什么不可以,
判断右下的话是先把右下判断后再更改值，
这样为什么不可以
/*
flag=true;
help(i + 1, j);
help(i, j + 1);
test[i][j] = '0';
*/
flag=true;
test[i][j] = '0';
help(i + 1, j);
help(i, j + 1);
help(i-1,j);
help(i,j-1);
return flag;
} else {
return flag;
}
}
} 
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
boolean[][] flags = new boolean[grid.length][grid[0].length];
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
flags[i][j] = true;
if (isArea(grid, i, j, flags)) {
count++;
}
}
}
}
return count;
}
public boolean isArea(char[][] grid, int i, int j, boolean[][] flags) {
if (i > 0) {
if (flags[i - 1][j]) {
return false;
}
}
if (j > 0) {
if (flags[i][j - 1]) {
return false;
}
}
findland(grid, i, j, flags);
return true;
}
public void findland(char[][] grid, int i, int j, boolean[][] flags) {
if (i < grid.length - 1) {
if (grid[i + 1][j] == '1') {
flags[i + 1][j] = true;
findland(grid, i + 1, j, flags);
}
}
if (j < grid[0].length - 1) {
if (grid[i][j + 1] == '1') {
flags[i][j + 1] = true;
findland(grid, i, j + 1, flags);
}
}
}
} 
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
int islands = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == '1') {
islands++;
infect(grid,i,j);
}
}
}
return islands;
}
public void infect(char[][] grid, int i, int j) {
if(i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] != '1') {
return;
}
grid[i][j] = 2;
infect(grid,i-1,j);
infect(grid,i,j+1);
infect(grid,i+1,j);
infect(grid,i,j-1);
}
}
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
// write code here
int count = 0;
for (int i = 0; i < grid.length; i ++) {
for (int j = 0; j < grid[0].length; j ++) {
if (grid[i][j] == '1') {
count ++;
dfs(grid, i, j);
}
}
}
return count;
}
public void dfs(char[][] grid, int i, int j) {
if (grid[i][j] == '0') {
return;
} else {
grid[i][j] = '0';
}
if (i >= 1) dfs(grid, i - 1, j);
if (j >= 1) dfs(grid, i, j - 1);
if (i < grid.length - 1) dfs(grid, i + 1, j);
if (j < grid[0].length - 1) dfs(grid, i, j + 1);
}
} 
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
//bfs，深度优先遍历
//是递归，给好边界条件
//每个元素有多个选择
//dfs，能写出来就行，不用考虑时间复杂度
public int solve (char[][] grid) {
// write code here
int r = grid.length-1, c = grid[0].length-1;
int res = 0;
for(int i = 0; i <= r; i++){
for(int j = 0; j <= c; j++){
if(grid[i][j] == '1'){
res++;
//该元素连通后，会把旁边是1的改变为0
//直接修改grid[][]就可以，不用设置是否访问的数组
dfs(grid, i, j);
}
}
}
return res;
}
//dfs是递归的
//考虑dfs的边界
public void dfs(char[][] grid, int i, int j){
//i和j超出边界，或搜索到0
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
if(grid[i][j] == '1') grid[i][j] = '0';
dfs(grid, i, j-1);
dfs(grid, i, j+1);
dfs(grid, i-1, j);
dfs(grid, i+1, j);
}
} import java.util.*;
public class Solution {
int count = 0;
boolean[][] search;
public int solve (char[][] grid) {
int m = grid.length, n = grid[0].length;
search = new boolean[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j]=='1' && !search[i][j]){
count++;
bfs(grid, i, j);
}
}
}
return count;
}
public void bfs(char[][] grid, int i, int j){
int m = grid.length, n = grid[0].length;
if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0' || search[i][j]) return;
search[i][j] = true;
bfs(grid, i+1, j);
bfs(grid, i-1, j);
bfs(grid, i, j+1);
bfs(grid, i, j-1);
}
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
