fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. QUESTION IN SIMPLE WORDS
  6. ------------------------
  7. Grid contains:
  8. - 2 = start
  9. - 3 = finish
  10. - 1 = special cell, must visit at least one
  11. - 4 = blocked
  12. - others = normal usable cells
  13.  
  14. You may revisit cells.
  15. But cost is counted only the FIRST time a cell is used.
  16.  
  17. So the real goal is:
  18. Find a valid walk from 2 to 3 that touches at least one 1
  19. while using the minimum number of distinct cells.
  20.  
  21. ------------------------------------------------------------
  22. BRUTE FORCE IDEA
  23. ------------------------------------------------------------
  24. Try all possible walks from start to finish.
  25. Keep only those that:
  26. - reach 3
  27. - touch at least one 1
  28.  
  29. For each walk, count how many distinct cells were used.
  30.  
  31. ------------------------------------------------------------
  32. WHY BRUTE FORCE IS TOO SLOW
  33. ------------------------------------------------------------
  34. The number of possible walks is huge.
  35. Even a small grid can have too many possibilities.
  36.  
  37. ------------------------------------------------------------
  38. OPTIMIZED IDEA
  39. ------------------------------------------------------------
  40. Convert every usable cell into a graph node.
  41.  
  42. We need a connected structure that covers:
  43. - start
  44. - finish
  45. - at least one '1'
  46.  
  47. We use a small DP on bitmasks:
  48. 1 -> start is covered
  49. 2 -> finish is covered
  50. 4 -> some '1' is covered
  51.  
  52. So mask = 7 means all requirements are satisfied.
  53.  
  54. dp[mask][v] =
  55. minimum number of distinct cells needed for a connected structure
  56. ending at node v and already covering the things in mask
  57. */
  58.  
  59. int minDistinctCells(vector<vector<int>> grid) {
  60.     int n = grid.size();
  61.     int m = grid[0].size();
  62.  
  63.     vector<vector<int>> id(n, vector<int>(m, -1));
  64.     vector<pair<int, int>> cells;
  65.  
  66.     int start = -1, finish = -1;
  67.     vector<int> ones;
  68.  
  69.     // Give each usable cell a graph node id
  70.     for (int i = 0; i < n; i++) {
  71.         for (int j = 0; j < m; j++) {
  72.             if (grid[i][j] == 4) continue;
  73.             id[i][j] = (int)cells.size();
  74.             cells.push_back({i, j});
  75.         }
  76.     }
  77.  
  78.     int V = (int)cells.size();
  79.     if (V == 0) return -1;
  80.  
  81.     vector<vector<int>> adj(V);
  82.     int dx[4] = {-1, 1, 0, 0};
  83.     int dy[4] = {0, 0, -1, 1};
  84.  
  85.     // Build graph edges for 4-direction movement
  86.     for (int v = 0; v < V; v++) {
  87.         auto [x, y] = cells[v];
  88.  
  89.         if (grid[x][y] == 2) start = v;
  90.         if (grid[x][y] == 3) finish = v;
  91.         if (grid[x][y] == 1) ones.push_back(v);
  92.  
  93.         for (int dir = 0; dir < 4; dir++) {
  94.             int nx = x + dx[dir];
  95.             int ny = y + dy[dir];
  96.  
  97.             if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
  98.             if (id[nx][ny] == -1) continue;
  99.  
  100.             adj[v].push_back(id[nx][ny]);
  101.         }
  102.     }
  103.  
  104.     if (start == -1 || finish == -1 || ones.empty()) return -1;
  105.  
  106.     const int INF = 1e9;
  107.     vector<vector<int>> dp(8, vector<int>(V, INF));
  108.  
  109.     // Base states
  110.     dp[1][start] = 1;
  111.     dp[2][finish] = 1;
  112.     for (int v : ones) dp[4][v] = 1;
  113.  
  114.     for (int mask = 1; mask < 8; mask++) {
  115.         // Merge smaller masks at the same ending node
  116.         for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
  117.             int other = mask ^ sub;
  118.             if (sub > other) continue;
  119.  
  120.             for (int v = 0; v < V; v++) {
  121.                 if (dp[sub][v] == INF || dp[other][v] == INF) continue;
  122.  
  123.                 // -1 because node v was counted twice
  124.                 dp[mask][v] = min(dp[mask][v], dp[sub][v] + dp[other][v] - 1);
  125.             }
  126.         }
  127.  
  128.         // Spread this state through the graph
  129.         priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  130.  
  131.         for (int v = 0; v < V; v++) {
  132.             if (dp[mask][v] < INF) pq.push({dp[mask][v], v});
  133.         }
  134.  
  135.         while (!pq.empty()) {
  136.             auto [dist, u] = pq.top();
  137.             pq.pop();
  138.  
  139.             if (dist != dp[mask][u]) continue;
  140.  
  141.             for (int v : adj[u]) {
  142.                 if (dp[mask][v] > dp[mask][u] + 1) {
  143.                     dp[mask][v] = dp[mask][u] + 1;
  144.                     pq.push({dp[mask][v], v});
  145.                 }
  146.             }
  147.         }
  148.     }
  149.  
  150.     int ans = INF;
  151.     for (int v = 0; v < V; v++) {
  152.         ans = min(ans, dp[7][v]);
  153.     }
  154.  
  155.     return ans == INF ? -1 : ans;
  156. }
  157.  
  158. int main() {
  159.     vector<vector<int>> grid = {
  160.         {2, 0, 1},
  161.         {0, 4, 0},
  162.         {0, 0, 3}
  163.     };
  164.  
  165.     cout << minDistinctCells(grid) << '\n';
  166.     return 0;
  167. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/w6cR1s
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!