首页 > 试题广场 >

三国鼎立

[编程题]三国鼎立

热度指数：777 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在 $n*m$ 的棋盘格状土地上盘踞着三个国家的若干股势力，上下左右相邻的属于同一个国家的土地被认为是同一股势力。现在想知道，土地上总共有多少股势力？

数据范围： $1 \le n,m \le 100 \$
要求：空间复杂度 $O(n^2) \$ ，时间复杂度 $O(n^2) \$

输入描述:

第一行两个正整数，土地宽，长；
接下来一个个矩阵，今包含，表示土地上的国家分布。

输出描述:

一个正整数，势力股数。

示例1

输入

输出

说明

11
1
是1国的一块势力
 22
222
是2国一块势力
3
3333
是3国一块势力
  111
是1国的另一块势力
总共4块势力

示例2

输入

2 2
11
11

输出

备注:

算法知识视频讲解

pein531

利用深度优先搜索求解，对于某一轮搜索，其停止条件为：

1.坐标越界；

2.势力发生改变；

3.本次位置已经走过。

每遇到一次能进行深搜的位置，势力的计数就加一

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        char[][] grid = new char[n][m];
        for(int i = 0; i < n; i++)
            grid[i] = br.readLine().trim().toCharArray();
        int count = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)
                if(grid[i][j] != '0') {
                    count ++;
                    dfs(grid, i, j, grid[i][j]);
                }
        }
        System.out.println(count);
    }
    
    private static void dfs(char[][] grid, int x, int y, char influence) {
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0' || grid[x][y] != influence)
            return;
        grid[x][y] = '0';
        dfs(grid, x + 1, y, influence);
        dfs(grid, x - 1, y, influence);
        dfs(grid, x, y + 1, influence);
        dfs(grid, x, y - 1, influence);
    }
}

编辑于 2021-08-11 14:21:11 回复(2)

宋朝栗子

#include<iostream>
#include<vector>
#include<string>

using namespace std;

void dfs(vector<vector<char>> &grids, int x, int y, char target) {
    if (x < 0 || x >= grids.size() || y < 0 || y >= grids[0].size() || grids[x][y] != target) {
        return;
    }
    grids[x][y] = '#';
    
    int incx[] = {-1, 1, 0, 0};
    int incy[] = {0, 0, -1, 1};
    for (int i = 0; i < 4; ++i) {
        dfs(grids, x + incx[i], y + incy[i], target);
    }
}

int main(){
    int m, n;
    string tmp;
    
    cin >> m >> n;
    vector<vector<char>> grids(m, vector<char>(n));
    for (int i = 0; i < m; ++i) {
        cin >> tmp;
        for (int j = 0; j < n; ++j) {
            grids[i][j] = tmp[j];
        }
    }
    
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grids[i][j] != '#') {
                dfs(grids, i, j, grids[i][j]);
                res += 1;
            }
        }
    }
    cout << res;
    return 0;
}

编辑于 2021-07-14 20:30:42 回复(0)

Lee8106

广度优先

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
void bfs(int power, int i, int j, vector<vector<int>>& board, vector<vector<bool>>& seen)
{
    if (i < 0 || i >= seen.size() || j < 0 || j >= seen[0].size())
    {
        return;
    }
    if (seen[i][j] == 1)
    {
        return;
    }
    else
    {
        if (power == board[i][j])
        {
            seen[i][j] = 1;
            bfs(power, i + 1, j, board, seen);
            bfs(power, i - 1, j, board, seen);
            bfs(power, i, j + 1, board, seen);
            bfs(power, i, j - 1, board, seen);
        }
    }
}
 
int main()
{
    int ans = 0;
    int n, m;
    cin >> n >> m;
    vector<vector<int>> board(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        string chess;
        cin >> chess;
        for (int j = 0; j < m; j++)
        {
            board[i][j] = chess[j] - '0';
        }
    }
    vector<vector<bool>> seen(n, vector<bool>(m, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (seen[i][j])
            {
                continue;
            }
            else
            {
                bfs(board[i][j], i, j, board, seen);
                ans++;
            }
        }
    }
    cout << ans << endl;
}

发表于 2021-08-25 23:40:18 回复(0)

Joker-1111

JS V8版本

let line1 = readline().split(' ').map(Number);
let n = line1[0], m = line1[1];
let lines = [], tmp;
while(tmp = readline()){
    lines.push(tmp.split('').map(Number));
}
let count = 0;
function dfs(lines, i, j, tmp){
    if(i < 0 || i >= lines.length || j < 0 || j >= lines[0].length || lines[i][j] == 0 || lines[i][j] != tmp)return
    lines[i][j] = 0;
    dfs(lines, i, j+1, tmp);
    dfs(lines, i, j-1, tmp);
    dfs(lines, i+1, j, tmp);
    dfs(lines, i-1, j, tmp);
}
for(let i=0; i<n; i++){
    for(let j=0; j<m; j++){
        if(lines[i][j] != 0){
            dfs(lines, i, j, lines[i][j]);
            count += 1;
        }
    }
}
console.log(count);

发表于 2022-04-07 10:07:41 回复(0)

alexleslie

广度优先遍历

package main
 
import (
    "fmt"
    "strings"
    "strconv"
)
 
func main(){
    var n, m int
    fmt.Scan(&n)
    fmt.Scan(&m)
     
    fig := make([][]int, n)
    for i := range fig {
        var t string
        fmt.Scan(&t)
        t_new := strings.Split(t, "")
        temp := make([]int, m)
        for k := range t_new{
            temp[k], _ = strconv.Atoi(t_new[k])
        }
        fig[i] = temp
    }
     
    dict := make(map[int]bool)
    
    var trav func(x, y, num int)
    trav = func(x, y, num int) {
        if x < 0 || y < 0 || x >= n || y >=m || fig[x][y] != num {
            return
        }
        id := random(x,y)
        if dict[id] == true {
            return
        }else{
            dict[id] = true
        }
        trav(x-1, y, num)
        trav(x+1, y, num)
        trav(x, y-1, num)
        trav(x, y+1, num)
    }
    r := 0
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            id := random(i, j)
            if dict[id] == true {
                continue
            }else{
                r += 1
                trav(i,j,fig[i][j])
            }
        }
    }
    fmt.Print(r)
}

func random(x, y int) int  {
    return x * 65555 - y*201 + x % (y+1)
}

发表于 2022-03-05 01:53:40 回复(0)

好名字--

import java.util.*;
public class Main{
    static int ans[][];
    static int n,m;
    public static void main(String args[]){
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        m=scan.nextInt();
        int num=0;
        ans=new int[n+2][m+2];
        for(int i=1;i<=n;i++){
                String cur=scan.next();
                for(int j=0;j<m;j++){
                    ans[i][j+1]=cur.charAt(j);
                }
        }
 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(ans[i][j]!=0) {num++; dfs(i,j,ans[i][j]);}
            }
        }
        System.out.print(num);
    }
    public static void dfs(int i,int j,int curr){
        if(i>n||i<1||j>m||j<1)return;
        if (ans[i][j]==0) return;
        if (curr!=ans[i][j]) return;
        ans[i][j]=0;
        dfs(i+1,j,curr);
        dfs(i-1,j,curr);
        dfs(i,j+1,curr);
        dfs(i,j-1,curr);
    }
}

发表于 2021-09-20 19:56:55 回复(0)

Yejf

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> &a, int x, int y, int val) {
	if(a[x][y] != val) return;
	a[x][y] = 0;
	if(x+1 < a.size()) dfs(a, x+1, y, val);
	if(y+1 < a[0].size()) dfs(a, x, y+1, val);
	if(x-1 >= 0) dfs(a, x-1, y, val);
	if(y-1 >= 0) dfs(a, x, y-1, val);
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	int n, m; cin >> n >> m;

	vector<vector<int>> a(n, vector<int>(m));
	for(int i=0; i<n; ++i){
		string line; cin >> line;
		for(int j=0; j<m; ++j) a[i][j] = line[j] - '0';
	} 

	int res = 0;
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j){
		if(a[i][j] ==0) continue;
		++res;
		dfs(a, i, j, a[i][j]);
	}

	cout << res << endl;
	return 0;
}

发表于 2021-05-22 00:51:16 回复(0)

loxiii

经典岛屿问题，参考力扣岛屿问题几乎一模一样的做法

import java.util.Scanner;

public class sanguodingli {

    static int[] x = new int[]{0,1,0,-1};
    static int[] y = new int[]{1,0,-1,0};


    public static int jayha(int n,int m,char[][] pro){
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(pro[i][j]!='-'){
                    printer(i,j,pro,pro[i][j]);
                    res++;
                }
            }
        }
        return res;
    }

    public static void printer(int i,int j,char[][] pro,char ques){
        //System.out.println(i+"   "+j);
        pro[i][j] = '-';
        for (int k = 0; k < 4; k++) {
            if(i+x[k]<pro.length&&
                    j+y[k]<pro[0].length&&
                    i+x[k]>=0&&
                    j+y[k]>=0&&
                    pro[i+1][j]== ques)
                printer(i+1,j,pro,ques);
        }



    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        char[][] pro = new char[m][n];
        for (int i = 0; i < m; i++) {
            pro[i] = scanner.next().toCharArray();
        }

        int jayha = jayha(n, m, pro);
        System.out.println(jayha);
    }
}

发表于 2021-05-15 10:45:45 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师腾讯音乐娱乐集团大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

8条回答 31收藏 2703浏览

通过挑战的用户

阿楠QQ

2022-10-24 10:37:15
ahujch

2022-09-08 18:06:18
牛客49283...

2022-09-08 17:42:26
牛客74694...

2022-09-08 16:10:20
练习时长两年半的农具

2022-09-08 10:48:15

三国鼎立

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题