1 条题解
-
0
#include <iostream> #include <vector> #include <queue> using namespace std; vector<vector<int>> g(1010, vector<int>(1010, 0)); vector<vector<int>> s(1010, vector<int>(1010, 0)); int dx[] = {0, 0, -1, 1}; int dy[] = {1, -1, 0, 0}; int n, m; int st, ed; int ans = 1; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void bfs() { queue<pair<int,int> > q; q.push({st, ed}); s[st][ed] = 1; while(q.size()) { auto t = q.front(); q.pop(); for(int i = 0; i < 4; ++ i) { int x = t.first + dx[i], y = t.second + dy[i]; if(x >= 0 && x < n && y >= 0 && y < m) { if(!s[x][y] && gcd(g[t.first][t.second], g[x][y]) > 1) { s[x][y] = 1; q.push({x, y}); ans ++; } } } } } void solve() { cin >> n >> m; for(int i = 0; i < n; ++ i) { for(int j = 0; j < m; ++ j) { scanf("%d", &g[i][j]); } } cin >> st >> ed; st -- ,ed --; bfs(); cout << ans << '\n'; } int main() { solve(); return 0; }
- 1
信息
- ID
- 5514
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 3
- 上传者