fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int, int>> get_factors(int x, int M, int N, unordered_map<int, vector<pair<int, int>>>& factor_cache) {
  5.     if (factor_cache.find(x) != factor_cache.end()) {
  6.         return factor_cache[x];
  7.     }
  8.  
  9.     vector<pair<int, int>> factors;
  10.     for (int a = 1; a * a <= x; ++a) {
  11.         if (x % a == 0) {
  12.             int b = x / a;
  13.             if (a <= M && b <= N) factors.push_back({a, b});
  14.             if (b <= M && a <= N && a != b) factors.push_back({b, a});
  15.         }
  16.     }
  17.  
  18.     factor_cache[x] = factors; 
  19.     return factors;
  20. }
  21.  
  22. int main() {
  23.     int M, N;
  24.     cin >> M >> N;
  25.  
  26.  
  27.     vector<vector<int>> grid(M + 1, vector<int>(N + 1));
  28.     for (int i = 1; i <= M; ++i) {
  29.         for (int j = 1; j <= N; ++j) {
  30.             cin >> grid[i][j];
  31.         }
  32.     }
  33.  
  34.  
  35.     queue<pair<int, int>> q;
  36.     q.push({1, 1});
  37.  
  38.  
  39.     vector<vector<bool>> visited(M + 1, vector<bool>(N + 1, false));
  40.     visited[1][1] = true;
  41.  
  42.     unordered_map<int, vector<pair<int, int>>> factor_cache;
  43.  
  44.     while (!q.empty()) {
  45.         auto [r, c] = q.front();
  46.         q.pop();
  47.  
  48.         if (r == M && c == N) {
  49.             cout << "yes" << endl;
  50.             return 0;
  51.         }
  52.  
  53.  
  54.         int value = grid[r][c];
  55.         vector<pair<int, int>> jumps = get_factors(value, M, N, factor_cache);
  56.  
  57.  
  58.         for (auto [a, b] : jumps) {
  59.             if (!visited[a][b]) {
  60.                 visited[a][b] = true;
  61.                 q.push({a, b});
  62.             }
  63.         }
  64.     }
  65.  
  66.     cout << "no" << endl;
  67.     return 0;
  68. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
3
4
3 10 8 14
1 11 12 12
6 2 3 9
stdout
copy 
yes
https://ideone.com/Dyq6wn
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!