对数组进行逐行查找,找到由数字1 表示的封闭图形的最上端一行的最左边一个点(其数组行下标应该是最小的),用P0 表示。P0 是边界跟踪的起始点。定义变量dir 表示上述“关于方向码的概念”中的8 个方向,所以dir 的取值范围是 0,1 … 7 ,注意,后面的计算过程,有dir 对8 的模(求余)运算。C++代码
时间: 2024-03-01 07:54:38 浏览: 14
以下是一个基于C++语言的实现,用于在数组中查找由数字1表示的封闭图形的最上端一行的最左边一个点:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义方向码
const int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
// 判断一个点是否在数组范围内
bool inRange(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
// 从起始点开始进行边界跟踪
vector<vector<int>> boundaryTrace(vector<vector<int>>& arr, int startX, int startY) {
int rows = arr.size();
int cols = arr[0].size();
vector<vector<int>> trace;
trace.push_back({startX, startY});
int curX = startX;
int curY = startY;
int curDir = 0;
while (true) {
// 尝试转向
bool found = false;
for (int i = 0; i < 8; i++) {
int newDir = (curDir + i) % 8;
int newX = curX + dir[newDir][0];
int newY = curY + dir[newDir][1];
if (inRange(newX, newY, rows, cols) && arr[newX][newY] == 1) {
curX = newX;
curY = newY;
curDir = newDir;
trace.push_back({curX, curY});
found = true;
break;
}
}
// 如果无法转向,结束边界跟踪
if (!found) {
break;
}
}
return trace;
}
// 查找由数字1表示的封闭图形的最上端一行的最左边一个点
vector<int> findTopLeftPoint(vector<vector<int>>& arr) {
int rows = arr.size();
int cols = arr[0].size();
// 找到第一个数字1的位置
int startX = -1;
int startY = -1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (arr[i][j] == 1) {
startX = i;
startY = j;
break;
}
}
if (startX != -1) {
break;
}
}
if (startX == -1) {
// 数组中没有数字1
return {-1, -1};
}
// 从第一个数字1的位置开始进行边界跟踪,找到封闭图形的最上端一行的最左边一个点
vector<vector<int>> trace = boundaryTrace(arr, startX, startY);
int minX = rows, minY = cols;
for (auto& p : trace) {
if (p[0] < minX || (p[0] == minX && p[1] < minY)) {
minX = p[0];
minY = p[1];
}
}
return {minX, minY};
}
int main() {
vector<vector<int>> arr = {{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 1, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0}};
vector<int> topLeft = findTopLeftPoint(arr);
cout << "Top-left point: (" << topLeft[0] << ", " << topLeft[1] << ")" << endl;
return 0;
}
```
这个代码中,我们首先定义了方向码数组 `dir`,用于表示8个方向。然后,我们实现了一个 `inRange` 函数,用于判断一个点是否在数组范围内;一个 `boundaryTrace` 函数,用于从起始点开始进行边界跟踪,并返回跟踪的结果;以及一个 `findTopLeftPoint` 函数,用于查找由数字1表示的封闭图形的最上端一行的最左边一个点。
在 `findTopLeftPoint` 函数中,我们首先找到第一个数字1的位置,并从该位置开始进行边界跟踪,得到封闭图形的轮廓。然后,我们遍历轮廓上的所有点,找到最上面一行的最左边一个点,并将其作为结果返回。
在 `main` 函数中,我们创建了一个测试数组 `arr`,并调用 `findTopLeftPoint` 函数,在控制台输出结果。