有谁会？！！

常规
1

6. 被幸福包裹的数

XJOI - 题目ID：9433必做题50分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

传说数字1代表幸福，请找出矩阵种被幸福包裹的数，并把它设置为2.

输入格式

每组测试数据第一行一个整数n(1≤n≤30)
接下来n行，由0和1组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。

输出格式

已经填好数字2的完整方阵。

样例

Input 1

6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1

Output 1

0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1

Input 2

5 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1

Output 2

1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1

样例解释

测试样例1解释：
这是一组方阵，圈内的1表示被幸福包裹的数，根据题目要求，将这些幸福的数设置为2，然后返回结果。

测试样例2解释：
这是一组方阵，所有的数都被幸福包裹，所以将所有的数设置为2，然后返回结果。

4 个赞
2

这个题很像水坑计数
http://poj.org/problem?id=2386
可以使用BFS从里往外搜
这是我的水坑计数答案（我懒得改）

#include <bits/stdc++.h> 
using namespace std;
bool isValid(int x, int y, int n, int m, vector<vector<bool>>& visited) {
    return (x >= 0 && y >= 0 && x < n && y < m && !visited[x][y]);
}
void BFS(vector<string>& land, int n, int m, int x, int y, vector<vector<bool>>& visited) {
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    queue<pair<int,int>> q;
    visited[x][y] = true;
    q.push({x, y});
    while (!q.empty()) {
        int currX = q.front().first;
        int currY = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int newX = currX + dx[i];
            int newY = currY + dy[i];
            if (isValid(newX, newY, n, m, visited) && land[newX][newY] == '1') {
                visited[newX][newY] = true;
                q.push({newX, newY});
            }
        }
    }
}

int countDistinctPools(vector<string>& land, int n, int m) {
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int distinctPools = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && land[i][j] == '1') {
                BFS(land, n, m, i, j, visited);
                distinctPools++;
            }
        }
    }
    
    return distinctPools;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<string> land(n);
    for (int i = 0; i < n; i++) {
        cin >> land[i];
    }
    
    int distinctPools = countDistinctPools(land, n, m);
    
    cout << distinctPools << endl;
    
    return 0;
}
3 个赞