本文最后更新于 704 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
BFS
。
- 难点一,处理地图坐标和转换:
- 题目的地图坐标和二维数组坐标不照应;
- 则,第
a
排 b
列需要转换为 mp[n - b][a - 1]
。
- 难点二,记录消耗的天数:
- 由于
BFS
搜索不能记录当前搜索的是第几层;
- 则,考虑在新搜索到的点额外增加参数
w
,来记录该点在第几周被感染;
- 最后用
res
维护最大的 w
即为答案。
- 最后,搜索时要枚举八个方向,利用偏移量数组解决即可。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 210; |
| |
| char mp[N][N]; |
| bool vis[N][N]; |
| |
| int n, m, a, b, res; |
| |
| int dx[] = {0, 0, 1, 1, -1, -1, 1, -1}, dy[] = {1, -1, 1, -1, 1, -1, 0, 0}; |
| |
| struct stu{ |
| int x, y, w; |
| }; |
| |
| int bfs(int l, int r, int w){ |
| |
| queue<stu> st; |
| st.push({l, r, w}); |
| vis[l][r] = 1; |
| |
| while(!st.empty()){ |
| stu p = st.front(); st.pop(); |
| res = max(res, p.w); |
| for(int i = 0; i < 8; i ++){ |
| int l = p.x + dx[i], r = p.y + dy[i]; |
| if(l >= 0 && l < n && r >= 0 && r < m && !vis[l][r] && mp[l][r] == '.'){ |
| vis[l][r] = 1; |
| st.push({l, r, p.w + 1}); |
| } |
| } |
| } |
| return res; |
| } |
| |
| void solve(){ |
| cin >> m >> n >> a >> b; |
| for(int i = 0; i < n; i ++) cin >> mp[i]; |
| mp[n - b][a - 1] = 'M'; |
| cout << bfs(n - b, a - 1, 0) << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |