1 条题解

  • 0
    @ 2024-11-24 23:55:55
    #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
    上传者