题解

题面描述

国家的领土被看作由 $n$ 行 $m$ 列构成的矩阵，每个单元格中都有一个部落，用小写字母表示，记为 $s_{i,j}$。
若同一部族的任意两个相邻（四相邻，即上下左右）的单元格直接连接，则这些单元格构成一个 亲密部落。
对于任意一个单元格，要求计算其所在的亲密部落与多少个不同的非本部族的部落（敌对部落）相邻。
输入给定 $n,\; m$ 以及 $n$ 行字符串，每行长度为 $m$，输出同样 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$ 单元格所在的亲密部落与多少个不同敌对部落相邻。

思路

本题利用图论中的连通域思想，通过深度优先搜索或广度优先搜索，将相同部族且四相邻的单元格划分到同一亲密部落中，同时在遍历过程中记录每个连通域边界上与之相邻的不同部族，最终统计出每个连通域的敌对部落数量，并输出对应于每个单元格的结果。

1. 连通域划分
   利用 深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 对网格进行遍历，将同一部族且通过四相邻相连的单元格划分到同一个连通域，也就是同一个亲密部落。
   设 $id[i][j]$ 表示 $(i,j)$ 所在的连通域编号，同时记录每个连通域的部族字母。

2. 敌对部落统计
   对每个连通域，在遍历过程中考察其边界邻居（相邻的单元格），若相邻单元格属于不同的部族，则将该部族记录到该连通域的集合中。
   最后，每个连通域的敌对部落数量即为集合中不同部族的数量。

3. 结果输出
   对于每个单元格，直接输出其所在连通域的敌对部落数量。

时间复杂度为 $O(n \times m)$，适用于 $n,\; m \le 500$。

C++

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++){
        cin >> grid[i];
    }
    
    // 用于标记每个单元格所属的连通域编号，初始值为 -1 表示未访问
    vector<vector<int>> comp(n, vector<int>(m, -1));
    // 保存每个连通域敌对部落数量
    vector<int> enemyCount;
    // 保存每个连通域的部族字符
    vector<char> tribe;
    
    int compId = 0;
    // 四个方向的移动
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    
    // 使用 BFS 进行连通域搜索
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if(comp[i][j] == -1){
                // 当前连通域的部族
                char currentTribe = grid[i][j];
                // 保存该连通域中相邻不同部族的集合
                set<char> enemySet;
                // BFS 队列
                queue<pair<int,int>> q;
                q.push({i, j});
                comp[i][j] = compId;
                
                while(!q.empty()){
                    auto cur = q.front();
                    q.pop();
                    int x = cur.first, y = cur.second;
                    
                    // 遍历四个方向
                    for (int d = 0; d < 4; d++){
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        // 如果相邻单元格与当前单元格属于同一部族且未被访问，则加入队列
                        if(grid[nx][ny] == currentTribe && comp[nx][ny] == -1){
                            comp[nx][ny] = compId;
                            q.push({nx, ny});
                        }
                        // 如果部族不同，则记录敌对部落
                        else if(grid[nx][ny] != currentTribe){
                            enemySet.insert(grid[nx][ny]);
                        }
                    }
                }
                // 保存该连通域的敌对部落数量
                enemyCount.push_back(enemySet.size());
                tribe.push_back(currentTribe);
                compId++;
            }
        }
    }
    
    // 输出答案，每个单元格所在连通域的敌对部落数量
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cout << enemyCount[comp[i][j]] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Python

# -*- coding: utf-8 -*-
from collections import deque

def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

    # 读入 $n$ 和 $m$
    n, m = map(int, input().split())
    grid = [input().strip() for _ in range(n)]
    
    # 用于标记每个单元格所属的连通域，初始值为 -1 表示未访问
    comp = [[-1] * m for _ in range(n)]
    enemyCount = []  # 每个连通域的敌对部落数量
    tribe = []       # 每个连通域的部族字符

    compId = 0
    # 四个方向
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    
    # 使用 BFS 进行连通域搜索
    for i in range(n):
        for j in range(m):
            if comp[i][j] == -1:
                currentTribe = grid[i][j]  # 当前连通域的部族
                enemySet = set()  # 保存相邻的不同部族
                q = deque()
                q.append((i, j))
                comp[i][j] = compId
                
                while q:
                    x, y = q.popleft()
                    # 遍历四个方向
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if nx < 0 or nx >= n or ny < 0 or ny >= m:
                            continue
                        # 如果相邻单元格与当前部族相同且未访问，则加入队列
                        if grid[nx][ny] == currentTribe and comp[nx][ny] == -1:
                            comp[nx][ny] = compId
                            q.append((nx, ny))
                        # 如果部族不同，则记录敌对部落
                        elif grid[nx][ny] != currentTribe:
                            enemySet.add(grid[nx][ny])
                enemyCount.append(len(enemySet))
                tribe.append(currentTribe)
                compId += 1

    # 输出答案
    for i in range(n):
        res = []
        for j in range(m):
            res.append(str(enemyCount[comp[i][j]]))
        print(" ".join(res))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // BufferedReader 用于快速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int n = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++){
            String line = br.readLine();
            grid[i] = line.toCharArray();
        }
        
        // comp 数组用于标记每个单元格所属的连通域，初始值为 -1 表示未访问
        int[][] comp = new int[n][m];
        for (int[] row : comp)
            Arrays.fill(row, -1);
        
        // 存储每个连通域的敌对部落数量
        ArrayList<Integer> enemyCount = new ArrayList<>();
        // 存储每个连通域的部族字符
        ArrayList<Character> tribe = new ArrayList<>();
        
        int compId = 0;
        // 定义四个方向
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        // 使用 BFS 进行连通域搜索
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(comp[i][j] == -1){
                    char currentTribe = grid[i][j];
                    HashSet<Character> enemySet = new HashSet<>();
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    comp[i][j] = compId;
                    
                    while(!queue.isEmpty()){
                        int[] cur = queue.poll();
                        int x = cur[0], y = cur[1];
                        
                        // 遍历四个方向
                        for (int d = 0; d < 4; d++){
                            int nx = x + dx[d];
                            int ny = y + dy[d];
                            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                            if(grid[nx][ny] == currentTribe && comp[nx][ny] == -1){
                                comp[nx][ny] = compId;
                                queue.add(new int[]{nx, ny});
                            } else if(grid[nx][ny] != currentTribe){
                                enemySet.add(grid[nx][ny]);
                            }
                        }
                    }
                    enemyCount.add(enemySet.size());
                    tribe.add(currentTribe);
                    compId++;
                }
            }
        }
        
        // 输出答案
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                sb.append(enemyCount.get(comp[i][j])).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目内容

某国的领土可以看作$n$行$m$列的矩阵，一共$n×m$个单元格，每一个单元格中都有一个部落。

我们使用$(i,j)$ 表示矩阵中从上往下数第$i$行和从左往右数第$j$列的单元格，里面的部族名为小写字母$s_{i,j}$

同一个部族的成员如果彼此相邻，那么他们更进一步的被称作亲密部落。更具体地，若存在这样两个单元格$(x,y)$ 和$(p,q)$，使得 $s_{x,y}$ =$s_{p,q}$且$|x-p|+|y-q| =1$，那么我们称他们属于同一个亲密部落。

现在小红想让你回答，对于任意$(i,j)$这个单元格上的部族，其所在亲密部落与多少个非自己部族的部族相邻。

在本题中，我们认为两个单元格$(x,y)$和$(p,q)$ 是相邻的,当且仅当$|x-p|+|y-q| =1$(四相邻)。

输入描述

第一行两个整数$n,m(1 ≦n,m≦500)$代表国家的领土大小。

此后$n$行，第i行输入一个长度为$m$，由小写字母组成的字符串$s_i$，代表第$i$行的部落分布。

输出描述

输出$n$行，每行$m$个整数，第$i$行第$j$个整数代表$(i,j)$所在部落存在多少不同的敌对部落。

样例1

输入

3 3
baa
aab
cac

输出

1 2 2 
2 2 2
1 2 2

说明

在这个样例中，以$(1,2)$这个单元格上的'$a$'部落为例，其所在的亲密部落共包含$5$个单元格，分别是$(1,2)，(1,3),(2,1),(2,2),(3,2)$。与'$b$'、'$a$'部落相邻 自5个