m×n可数组成一个m×n的矩阵,水平或垂直相邻的两个数的距离为1,猎人和熊分别在一棵树下。如果猎人与熊之间没有其他的数,这当实现猎人就可以开枪打到熊。以人和胸的位置,试判断熊所在的位置是否安全。例:输入1 1 1 2 3 输出no C语言代码
时间: 2024-12-04 09:26:57 浏览: 14
679个超全地级市地理距离矩阵+286个地级市0-1相邻矩阵
这个问题描述的是一个二维数组的搜索问题,也被称为“棋盘上的捕熊者”或“安全岛”问题。给定一个m×n的矩阵,表示森林中的空地(0)和障碍物(非零),猎人在左上角,熊在右下角。如果在移动过程中,除了直接的上下左右四个方向之外,不存在空地可以到达熊的位置,那么熊就是安全的。在C语言中,你可以通过回溯法来解决这个问题。
下面是一个简单的C语言代码实现思路:
```c
#include <stdio.h>
#define ROW 5 // 矩阵的行数
#define COL 5 // 矩阵的列数
int matrix[ROW][COL]; // 定义矩阵
int visited[ROW][COL] = {0}; // 记录已访问位置
// 检查当前位置是否可达并安全
bool isSafe(int i, int j) {
if (i < 0 || i >= ROW || j < 0 || j >= COL || matrix[i][j]) return false;
if (visited[i][j]) return true; // 如果已经访问过,则不可达
visited[i][j] = 1; // 标记为已访问
if (i == ROW - 1 && j == COL - 1) // 到达熊的位置
return !anyAdjacent(i, j); // 检查周围是否有障碍
else
return isSafe(i + 1, j) || isSafe(i - 1, j) || isSafe(i, j + 1) || isSafe(i, j - 1);
}
// 检查某个坐标周围是否有障碍
bool anyAdjacent(int i, int j) {
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
if (dx != 0 || dy != 0)
if (!visited[i + dx][j + dy])
return true;
return false;
}
// 主函数
void checkSafety() {
printf("输入矩阵:\n");
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++)
scanf("%d", &matrix[i][j]);
}
if (isSafe(0, 0)) {
printf("输出: yes\n");
} else {
printf("输出: no\n");
}
}
int main() {
checkSafety();
return 0;
}
```
阅读全文