fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N;
  5. int grid[11][11];          // Maze grid
  6. bool visited[11][11];      // Mark visited cells
  7. int dr[4] = {-1, 1, 0, 0}; // Up, Down, Left, Right
  8. int dc[4] = {0, 0, -1, 1};
  9.  
  10. int bestJewels;
  11. vector<pair<int,int>> bestPath;
  12.  
  13. bool inBounds(int r, int c) {
  14.     return r >= 0 && r < N && c >= 0 && c < N;
  15. }
  16.  
  17. void dfs(int r, int c, int jewels, vector<pair<int,int>> &path) {
  18.     // If reached the exit, update best answer
  19.     if (r == N-1 && c == N-1) {
  20.         if (jewels > bestJewels) {
  21.             bestJewels = jewels;
  22.             bestPath = path;
  23.         }
  24.         return;
  25.     }
  26.  
  27.     // Explore neighbors
  28.     for (int k = 0; k < 4; k++) {
  29.         int nr = r + dr[k], nc = c + dc[k];
  30.         if (!inBounds(nr, nc) || visited[nr][nc] || grid[nr][nc] == 1)
  31.             continue;
  32.         visited[nr][nc] = true;
  33.         path.push_back({nr, nc});
  34.         int add = (grid[nr][nc] == 2 ? 1 : 0);
  35.  
  36.         dfs(nr, nc, jewels + add, path);
  37.  
  38.         path.pop_back();
  39.         visited[nr][nc] = false;
  40.     }
  41. }
  42.  
  43. void solve() {
  44.     cin >> N;
  45.     for (int i = 0; i < N; i++)
  46.         for (int j = 0; j < N; j++)
  47.             cin >> grid[i][j];
  48.  
  49.     memset(visited, false, sizeof(visited));
  50.     bestJewels = -1;
  51.     bestPath.clear();
  52.  
  53.     vector<pair<int,int>> path;
  54.     path.push_back({0,0});
  55.     visited[0][0] = true;
  56.     int startJewels = (grid[0][0] == 2 ? 1 : 0);
  57.  
  58.     dfs(0, 0, startJewels, path);
  59.  
  60.     // Output
  61.     cout << bestJewels << "\n";
  62.     cout << bestPath.size()<< "\n";
  63.     for (auto &p : bestPath)
  64.         cout << p.first + 1 << " " << p.second + 1 << "\n";
  65. }
  66.  
  67. int main() {
  68.     ios::sync_with_stdio(false);
  69.     cin.tie(nullptr);
  70.  
  71.     int T;
  72.     cin >> T;
  73.     while (T--) solve();
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
1
5
0 1 2 1 1
2 2 0 0 0
0 0 1 1 0 
0 2 1 1 2
0 2 1 2 0
stdout 
5
15
1 1
2 1
3 1
4 1
5 1
5 2
4 2
3 2
2 2
2 3
2 4
2 5
3 5
4 5
5 5
https://ideone.com/Ig5uYd
language:
C++14 (gcc 8.3)
created:
4 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!