题意分析

题目要求分析一张包含骰子的图像，识别每个骰子上的点数（X的连通区域数量），并按升序输出所有骰子的点数。

• 输入：图像由 .（背景）、*（骰子）、X（骰子上的点）组成，宽度 w 和高度 h 范围 5~50。
• 输出：按升序输出每个骰子的点数，如 1 2 2 4 表示四个骰子分别有 1、2、2、4 个点。

解题思路

1. 图像遍历：
   • 使用 DFS 遍历每个骰子区域（连通 * 或 X）。
   • 遇到 X 时，启动子 DFS 统计该点的连通区域（点数），并将 X 标记为已访问。
2. 点数统计：
   • 每发现一个 X 的连通区域，点数 count 加 1。
3. 排序输出：
   • 使用 qsort 对点数数组升序排序后输出。

代码实现

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

// 方向数组：上、右、下、左
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

// 检查坐标是否在图像范围内
bool isValid(int x, int y, int h, int w) {
    return x >= 0 && x < h && y >= 0 && y < w;
}

// 标记并返回连通区域的大小
int markRegion(vector<vector<char>>& img, int x, int y, char mark) {
    if (img[x][y] != '*' && img[x][y] != 'X') return 0;
    
    queue<pair<int, int>> q;
    q.push({x, y});
    img[x][y] = mark;
    int size = 1;
    
    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (isValid(nx, ny, img.size(), img[0].size()) && 
                (img[nx][ny] == '*' || img[nx][ny] == 'X')) {
                img[nx][ny] = mark;
                q.push({nx, ny});
                size++;
            }
        }
    }
    return size;
}

// 计算一个点（X连通区域）的大小
int countPip(vector<vector<char>>& img, int x, int y) {
    if (img[x][y] != 'X') return 0;
    
    queue<pair<int, int>> q;
    q.push({x, y});
    img[x][y] = '.';
    int size = 1;
    
    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (isValid(nx, ny, img.size(), img[0].size()) && 
                img[nx][ny] == 'X') {
                img[nx][ny] = '.';
                q.push({nx, ny});
                size++;
            }
        }
    }
    return size;
}

int main() {
    int w, h;
    int caseNum = 1;
    
    while (cin >> w >> h && (w != 0 || h != 0)) {
        vector<vector<char>> img(h, vector<char>(w));
        
        // 读取图像
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> img[i][j];
            }
        }
        
        vector<int> dicePips;
        set<pair<int, int>> diceRegions;
        
        // 标记所有骰子区域
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (img[i][j] == '*' || img[i][j] == 'X') {
                    // 标记骰子区域（用'D'表示）
                    int diceSize = markRegion(img, i, j, 'D');
                    if (diceSize > 10) { // 过滤太小的区域
                        diceRegions.insert({i, j});
                    }
                }
            }
        }
        
        // 处理每个骰子区域
        for (auto& pos : diceRegions) {
            int x = pos.first;
            int y = pos.second;
            
            // 重新标记骰子区域（用'*'恢复，便于处理点数）
            queue<pair<int, int>> q;
            q.push({x, y});
            img[x][y] = '*';
            
            while (!q.empty()) {
                int cx = q.front().first;
                int cy = q.front().second;
                q.pop();
                
                for (int i = 0; i < 4; i++) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (isValid(nx, ny, h, w) && img[nx][ny] == 'D') {
                        img[nx][ny] = '*';
                        q.push({nx, ny});
                    }
                }
            }
            
            // 计算该骰子的点数
            int pipCount = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (img[i][j] == 'X') {
                        int pipSize = countPip(img, i, j);
                        // 合理的点数大小（过滤噪声）
                        if (pipSize >= 1 && pipSize <= 20) {
                            pipCount++;
                        }
                    }
                }
            }
            
            if (pipCount >= 1 && pipCount <= 6) {
                dicePips.push_back(pipCount);
            }
        }
        
        // 排序并输出结果
        sort(dicePips.begin(), dicePips.end());
        cout << "Throw " << caseNum++ << endl;
        for (int i = 0; i < dicePips.size(); i++) {
            if (i > 0) cout << " ";
            cout << dicePips[i];
        }
        cout << endl << endl;
    }
    
    return 0;
}

### **关键点**
- **DFS 设计**：  
  - `DFS` 处理骰子连通区域，遇到 `X` 调用 `DFS_X` 统计点数。  
  - `DFS_X` 只处理 `X` 的连通区域，防止重复计数。  
- **边界处理**：图像周围填充 `.` 防止越界。  
- **排序输出**：使用 `qsort` 快速排序点数。  

### **复杂度分析**
- **时间**：O(w×h)，每个像素至多访问一次。  
- **空间**：O(w×h)，存储图像和递归栈。