赞
踩
dfs:深度优先遍历(红色)
bfs:宽度优先遍历
- class Solution {
- int[] dx = { 0, 0, 1, -1 };
- int[] dy = { 1, -1, 0, 0 };
-
- public int[][] floodFill(int[][] image, int sr, int sc, int color) {
- int prev = image[sr][sc]; // 统计刚开始的颜⾊
- if (prev == color)
- return image; // 处理边界情况
- int m = image.length, n = image[0].length;
- Queue<int[]> q = new LinkedList<>();
- q.add(new int[] { sr, sc });
- while (!q.isEmpty()) {
- int[] t = q.poll();
- int a = t[0], b = t[1];
- image[a][b] = color;
- // 上下左右四个⽅向
- for (int i = 0; i < 4; i++) {
- int x = a + dx[i], y = b + dy[i];
- if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {
- q.add(new int[] { x, y });
- }
- }
- }
- return image;
- }
- }
- class Solution {
- int[] dx = { 0, 0, -1, 1 };
- int[] dy = { 1, -1, 0, 0 };
- boolean[][] vis = new boolean[301][301];
- int m, n;
-
- public int numIslands(char[][] grid) {
- m = grid.length;
- n = grid[0].length;
- int ret = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == '1' && !vis[i][j]) {
- ret++;
- bfs(grid, i, j);
- }
- }
- }
- return ret;
- }
-
- public void bfs(char[][] grid, int i, int j) {
- Queue<int[]> q = new LinkedList<>();
- q.add(new int[] { i, j });
- vis[i][j] = true;
- while (!q.isEmpty()) {
- int[] t = q.poll();
- int a = t[0], b = t[1];
- for (int k = 0; k < 4; k++) {
- int x = a + dx[k], y = b + dy[k];
- if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' &&
- !vis[x][y]) {
- q.add(new int[] { x, y });
- vis[x][y] = true;
- }
- }
- }
- }
- }
- class Solution {
- int[] dx = { 0, 0, 1, -1 };
- int[] dy = { 1, -1, 0, 0 };
- boolean[][] vis = new boolean[51][51];
- int m, n;
-
- public int maxAreaOfIsland(int[][] grid) {
- m = grid.length;
- n = grid[0].length;
- int ret = 0;
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n; j++) {
- if (grid[i][j] == 1 && !vis[i][j]) {
- ret = Math.max(ret, bfs(grid, i, j));
- }
- }
- }
- return ret;
- }
-
- public int bfs(int[][] grid, int i, int j) {
- int count = 0;
- Queue<int[]> q = new LinkedList<>();
- q.add(new int[] { i, j });
- vis[i][j] = true;
- count++;
- while (!q.isEmpty()) {
- int[] t = q.poll();
- int a = t[0], b = t[1];
- for (int k = 0; k < 4; k++) {
- int x = a + dx[k], y = b + dy[k];
- if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 &&
- !vis[x][y]) {
- q.offer(new int[] { x, y });
- vis[x][y] = true;
- count++;
- }
- }
- }
- return count;
- }
- }
- class Solution {
- int n, m;
-
- public void solve(char[][] board) {
- n = board.length;
- if (n == 0) {
- return;
- }
- m = board[0].length;
- for (int i = 0; i < n; i++) {
- dfs(board, i, 0);
- dfs(board, i, m - 1);
- }
- for (int i = 1; i < m - 1; i++) {
- dfs(board, 0, i);
- dfs(board, n - 1, i);
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- if (board[i][j] == 'A') {
- board[i][j] = 'O';
- } else if (board[i][j] == 'O') {
- board[i][j] = 'X';
- }
- }
- }
- }
-
- public void dfs(char[][] board, int x, int y) {
- if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
- return;
- }
- board[x][y] = 'A';
- dfs(board, x + 1, y);
- dfs(board, x - 1, y);
- dfs(board, x, y + 1);
- dfs(board, x, y - 1);
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。