fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, a[1005][1005];
  5.  
  6. int BFS() {
  7.     int M[1005][1005] = {};
  8.     queue<pair<int, int>> q;
  9.     q.push({1, 1});
  10.     M[1][1] = 0;
  11.  
  12.     while (!q.empty()) {
  13.         auto [x, y] = q.front(); q.pop();
  14.  
  15.         if (x + a[x][y] <= n && !M[x + a[x][y]][y]) {
  16.             if (x + a[x][y] == n && y == m) return M[x][y] + 1;
  17.             M[x + a[x][y]][y] = M[x][y] + 1;
  18.             q.push({x + a[x][y], y});
  19.         }
  20.  
  21.         if (y + a[x][y] <= m && !M[x][y + a[x][y]]) {
  22.             if (x == n && y + a[x][y] == m) return M[x][y] + 1;
  23.             M[x][y + a[x][y]] = M[x][y] + 1;
  24.             q.push({x, y + a[x][y]});
  25.         }
  26.     }
  27.     return -1;
  28. }
  29.  
  30. int main() {
  31.     ios::sync_with_stdio(false); cin.tie(0);
  32.     int t; cin >> t;
  33.     while (t--) {
  34.         cin >> n >> m;
  35.         for (int i = 1; i <= n; ++i)
  36.             for (int j = 1; j <= m; ++j)
  37.                 cin >> a[i][j];
  38.         cout << BFS() << '\n';
  39.     }
  40.     return 0;
  41. }
  42.  
Success #stdin #stdout 0.01s 7548KB
comments (?)
stdin 
1
3 3
2 1 2
1 1 1 
1 1 1
stdout 
2
https://ideone.com/DqD2OH
language:
C++ (gcc 8.3)
created:
8 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!