计算鸭有一个 � ∗ � n∗n 的方格矩阵,每一个位置都有一个数字 0 或 1 ,所有数字 1 恰好围成了一个任意形状的闭合圈(围圈时只走上下左右 4 个方向)。现要求把闭合圈内的所有位置都填写成 2 ,请你给出填数后的矩阵。 Input 第一行一个整数 � n( 1 ≤ � ≤ 30 1≤n≤30)。 接下来 � n 行,由 0 和 1 组成 � × � n×n 的方阵。 保证方阵内只有一个闭合圈,圈内至少有一个 0。 Output 已经填好数字 2 的矩阵。 Sample input 1Copy 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 1Copy 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 c++代码,禁用vector
时间: 2024-01-02 19:04:51 浏览: 105
关于n×n棋盘填数问题的一个命题 (2005年)
在给定的方阵中,我们需要找到闭合圈起始位置。然后,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来将闭合圈内的所有位置填写为2。下面是使用深度优先搜索(DFS)的C++代码实现:
```cpp
#include <iostream>
const int MAX_N = 30;
int n;
int matrix[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
// 判断坐标是否在方阵内
bool isValid(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n);
}
// 使用深度优先搜索将闭合圈内的位置填写为2
void dfs(int x, int y) {
visited[x][y] = true;
matrix[x][y] = 2;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && matrix[nx][ny] == 1 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
int main() {
std::cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cin >> matrix[i][j];
}
}
// 找到闭合圈的起始位置
int startX = -1, startY = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
startX = i;
startY = j;
break;
}
}
if (startX != -1 && startY != -1) {
break;
}
}
// 使用深度优先搜索将闭合圈内的位置填写为2
dfs(startX, startY);
// 输出填好数字后的矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
std::cout << matrix[i][j] << " ";
}
std::cout << std::endl;
}
return 0;
}
```
你可以将输入数据放在标准输入中,然后运行程序,得到输出结果。输出表示填好数字后的矩阵。希望对你有帮助!
阅读全文