方格土地上有三个国家的多股势力，上下左右相邻的属于同一国家的代表一个势力，问一共有多少个势力
输入
4 4 #方格大小
1122
1222
3111
3333
输出
4 #一共四股势力
import java.util.*;class Solution{int dx[] = {-1, 0, 1, 0};int dy[] = {0, 1, 0, -1};public void dfs(int i, int j, int[][] map, int f){map[i][j] = 0;for(int x = 0; x < 4; x++){int m = i + dx[x];int n = j + dy[x];if(m >= 0 && m < map.length && n >= 0 && n < map[0].length && map[m][n] == f){dfs(m, n, map, f);}}}public int solve(int[][] map) {int m = map.length, n = map[0].length;int res = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(map[i][j] != 0){int f = map[i][j];res++;dfs(i, j, map, f);}}}return res;}}public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);int m = cin.nextInt();int n = cin.nextInt();int[][] map = new int[m][n];for(int i = 0; i < m; i++){String s = cin.next();for(int j = 0; j < n; j++){map[i][j] = s.charAt(j) - '0';}}int res = new Solution().solve(map);System.out.print(res);}}
130. 被围绕的区域
可以想象成两军交战，被完全包围的O就跑不出去了，就会被杀死变成X，但是如果有O在边界上，那么与边界O靠近的O士兵都可以撤退掉，不会变成X。
可以遍历四周边界，把能跑掉的O都标记成为 . 最后把跑不掉的O变成X即可
下面是自己写的，太挫了～～～
class Solution {
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
public void solve(char[][] board) {
int n = board.length;
if(n == 0) return;
int m = board[0].length;
if(n <= 2 || m <= 2) return;
for(int a = 0, b = 0, d = 0, i = 1; i <= n*m - (n - 2)*(m - 2); i++){
if(board[a][b] == 'O'){
run(board, a, b);
}
int x = a + dx[d];
int y = b + dy[d];
if(x < 0 || x >= n || y < 0 || y >= m){
d = d + 1;
x = a + dx[d];
y = b + dy[d];
}
a = x;
b = y;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'O'){
dfs(board, i, j);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == '.'){
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board, int a, int b){
board[a][b] = 'X';
for(int i = 0; i < 4; i++){
int x = a + dx[i];
int y = b + dy[i];
if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O'){
dfs(board, x, y);
}
}
}
public void run(char[][] board, int a, int b){
board[a][b] = '.';
for(int i = 0; i < 4; i++){
int x = a + dx[i];
int y = b + dy[i];
if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O'){
run(board, x, y);
}
}
}
}
把能跑掉的O标记成之后，杀掉跑不掉O的时候，就可以不使用大洪水灌溉算法了，直接两个for循环，把O变成X的同时，也将跑掉的.重新恢复成O
class Solution {
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
public void solve(char[][] board) {
int n = board.length;
if(n == 0) return;
int m = board[0].length;
if(n <= 2 || m <= 2) return;
for(int a = 0, b = 0, d = 0, i = 1; i <= n*m - (n - 2)*(m - 2); i++){
if(board[a][b] == 'O'){
run(board, a, b);
}
int x = a + dx[d];
int y = b + dy[d];
if(x < 0 || x >= n || y < 0 || y >= m){
d = d + 1;
x = a + dx[d];
y = b + dy[d];
}
a = x;
b = y;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}
if(board[i][j] == '.'){
board[i][j] = 'O';
}
}
}
}
public void run(char[][] board, int a, int b){
board[a][b] = '.';
for(int i = 0; i < 4; i++){
int x = a + dx[i];
int y = b + dy[i];
if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O'){
run(board, x, y);
}
}
}
}
遍历四周的时候，用的是螺旋矩阵的偏移量的方法，其实可以不用那么复杂
代码量上面差不多但是这个稍微好理解一点
class Solution {
int[] dx = new int[]{0, 1, 0, -1};
int[] dy = new int[]{1, 0, -1, 0};
public void solve(char[][] board) {
int n = board.length;
if(n == 0) return;
int m = board[0].length;
if(n <= 2 || m <= 2) return;
for (int i = 0; i < n; i ++ )
{
if (board[i][0] == 'O') run(board, i, 0);
if (board[i][m - 1] == 'O') run(board, i, m - 1);
}
for (int i = 0; i < m; i ++ )
{
if (board[0][i] == 'O') run(board, 0, i);
if (board[n - 1][i] == 'O') run(board, n - 1, i);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}
if(board[i][j] == '.'){
board[i][j] = 'O';
}
}
}
}
public void run(char[][] board, int a, int b){
board[a][b] = '.';
for(int i = 0; i < 4; i++){
int x = a + dx[i];
int y = b + dy[i];
if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O'){
run(board, x, y);
}
}
}
}
200. 岛屿数量
class Solution {
public int[] dx = new int[]{0, 1, 0, -1};
public int[] dy = new int[]{1, 0, -1, 0};
public void showGrid(char[][] grid){
int n = grid.length, m = grid[0].length;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
System.out.print(grid[i][j] +" ");
}
System.out.println();
}
}
public int numIslands(char[][] grid) {
int n = grid.length, m = grid[0].length;
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == '1'){
infect(grid, i, j);
res++;
// showGrid(grid);
}
// System.out.println("------------");
}
}
return res;
}
public void flood(char[][] grid, int i, int j){
grid[i][j] = '0';
for(int d = 0; d < 4; d++){
int a = i + dx[d];
int b = j + dy[d];
if(a >= 0 && a < grid.length && b >= 0 && b < grid[0].length && grid[a][b] == '1'){
flood(grid, a, b);
}
}
}
//感染函数
public void infect(char[][] grid, int i, int j){
if(i < 0 || i >= grid.length ||
j < 0 || j >= grid[0].length || grid[i][j] != '1'){
return;
}
grid[i][j] = '0';
infect(grid, i + 1, j);
infect(grid, i - 1, j);
infect(grid, i, j + 1);
infect(grid, i, j - 1);
}
}
若有收获，就点个赞吧
0 人点赞
