用c++解决 已知地图中的描述,是根据陆地和海水交错排布的,其中数字表示陆地的面积大小,0表示海水,被水围起来的区域称为“岛屿”,由于这次悟空手中有一件法宝可以使两块对角线相邻的陆地能够互通。已知师徒四人处在(m,n)点,请你按照八戒的提示编写程序,计算所在岛屿的面积。(注:地图使用二维数组存储,地图的大小不超过50*50)输入: m+1行第一行四个整数m,n,x,y其中m和n表示图的行和列,x和y表示你所处的横纵坐标。剩下m行每行n个数字分别代表陆地的面积大小 输出: 你所在岛屿的面积假设边界点为海水
时间: 2024-03-25 15:39:13 浏览: 60
这是一道典型的搜索题目,可以使用 DFS 或 BFS 进行求解。下面给出基于 BFS 的 C++ 代码实现:
```
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 55;
int n, m, x, y;
int g[N][N];
bool st[N][N];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct Node
{
int x, y;
};
int bfs(int x, int y)
{
queue<Node> q;
q.push({x, y});
st[x][y] = true;
int res = g[x][y];
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = 0; i < 8; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b] || !g[a][b]) continue;
st[a][b] = true;
res += g[a][b];
q.push({a, b});
}
}
return res;
}
int main()
{
cin >> n >> m >> x >> y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
cout << bfs(x, y) << endl;
return 0;
}
```
在这个例子中,我们使用二维数组 `g` 来存储地图信息,使用二维数组 `st` 来标记每个位置是否已经访问过。对于每个起点 `(x, y)`,我们使用 BFS 来遍历其所在的岛屿。在遍历的过程中,如果当前位置 `(x, y)` 超出地图边界或已经访问过或是海水,则跳过;否则,将当前位置标记为已访问,并计算当前位置的陆地面积 `res`。然后,依次遍历当前位置的八个相邻位置,并将其返回的陆地面积加到当前位置的陆地面积中。最后,返回当前位置的陆地面积 `res`,即为所在岛屿的面积。
阅读全文