1 条题解
-
0
- 2024-04-01
- BFS搜索
#include<bits/stdc++.h> void solve() { int n, m, x, y; std::cin >> n >> m >> x >> y; x--, y--; std::vector<std::string > s(n); for(int i = 0; i < n; i++) { std::cin >> s[i]; } int dxy[][2] = {0, 1, 0, -1, 1, 0, -1, 0}; int ans = 0; auto calc = [&](int x, int y) { int cnt = 0; for(int i = x + 1; i < n; i++) { if(s[i][y] == 'G') cnt++; else if(s[i][y] == '#') break; } for(int i = x - 1; i >= 0; i--) { if(s[i][y] == 'G') cnt++; else if(s[i][y] == '#') break; } for(int j = y + 1; j < m; j++) { if(s[x][j] == 'G') cnt++; else if(s[x][j] == '#') break; } for(int j = y - 1; j >= 0; j--) { if(s[x][j] == 'G') cnt++; else if(s[x][j] == '#') break; } return cnt; }; auto BFS =[&]() { std::queue<std::pair<int,int> > q; std::vector<std::vector<int> > vis(n, std::vector<int>(m)); q.push({x, y}); while(q.size()) { auto t = q.front(); q.pop(); auto nx = t.first, ny = t.second; int cnt = calc(nx, ny); if(ans < cnt) ans = cnt; for(int i = 0; i < 4; i++) { int dx = nx + dxy[i][0]; int dy = ny + dxy[i][1]; if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue; if(s[dx][dy] == '#' || s[dx][dy] == 'G') continue; if(vis[dx][dy]) continue; vis[dx][dy] = 1; q.push({dx, dy}); } } }; BFS(); std::cout << ans << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; while(t--) solve(); return 0; }
- 1
信息
- ID
- 134
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 2
- 标签
- 递交数
- 46
- 已通过
- 29
- 上传者