fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. using namespace std;
  6.  
  7. int n, m, check1 = 0, check2 = 0, check3 = 0;
  8. vector<pair<int, int>> res;
  9. vector<vector<int>> road;
  10.  
  11. bool findway(int row = 0, int col = 0)
  12. {
  13.     if (row == n - 1 && col == m - 1) {
  14.         if ((check1 > 0 && check2 > 0) || (check2 > 0 && check3 > 0) || (check1 > 0 && check3 > 0)) {
  15.             res.push_back(make_pair(n, m));
  16.             return true;
  17.         }
  18.         return false;
  19.     }
  20.     // right
  21.     if (col < m - 1 && road[row][col + 1] != -1) {
  22.         res.push_back(make_pair(row + 1, col + 2));
  23.         if (road[row][col + 1] == 1) ++check1;
  24.         else if (road[row][col + 1] == 2) ++check2;
  25.         else if (road[row][col + 1] == 3) ++check3;
  26.         if (findway(row, col + 1))
  27.             return true;
  28.     }
  29.     // down
  30.     if (row < n - 1 && road[row + 1][col] != -1) {
  31.         res.push_back(make_pair(row + 2, col + 1));
  32.         if (road[row][col + 1] == 1) ++check1;
  33.         else if (road[row][col + 1] == 2) ++check2;
  34.         else if (road[row][col + 1] == 3) ++check3;
  35.         if (findway(row + 1, col))
  36.             return true;
  37.     }
  38.     // backtrack
  39.     if (road[row][col] == 1) --check1;
  40.     else if (road[row][col] == 2) --check2;
  41.     else if (road[row][col] == 3) --check3;
  42.     res.pop_back();
  43.     return false;
  44. }
  45.  
  46. int main()
  47. {
  48.     cin >> n >> m;
  49.     road.resize(n);
  50.     res.push_back(make_pair(1, 1));
  51.     for (int i = 0; i < n; ++i) {
  52.         road[i].resize(m);
  53.         for (int j = 0; j < m; ++j)
  54.             cin >> road[i][j];
  55.     }
  56.     if (!findway()) cout << -1;
  57.     else {
  58.         int s = res.size();
  59.         for (int i = 0; i < s; ++i)
  60.             cout << res[i].first << " " << res[i].second << endl;
  61.     }
  62.     return 0;
  63. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 4
0 3 -1 2
3 3 3 3
3 1 3 0
stdout
copy 
-1
https://ideone.com/GntULZ
language:
C++ (gcc 8.3)
created:
7 years 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!