fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. /*
  7. QUESTION IN SIMPLE WORDS
  8. ------------------------
  9. We start at top-left and want to reach bottom-right.
  10.  
  11. Allowed moves:
  12. - left
  13. - right
  14. - down
  15.  
  16. Not allowed:
  17. - up
  18. - revisiting a cell
  19. - entering blocked cells
  20.  
  21. Goal:
  22. maximize number of cells visited on a valid path
  23.  
  24. Grid format in this code:
  25. '.' = open
  26. '#' = blocked
  27.  
  28. ------------------------------------------------------------
  29. BRUTE FORCE IDEA
  30. ------------------------------------------------------------
  31. Use backtracking:
  32. - try all valid paths
  33. - never revisit a cell
  34. - stop when we reach bottom-right
  35. - keep the longest valid path
  36.  
  37. ------------------------------------------------------------
  38. WHY BRUTE FORCE IS TOO SLOW
  39. ------------------------------------------------------------
  40. The number of possible paths grows very quickly.
  41. Backtracking becomes too slow.
  42.  
  43. ------------------------------------------------------------
  44. OPTIMIZED IDEA
  45. ------------------------------------------------------------
  46. Process row by row.
  47.  
  48. Inside one continuous open segment of a row:
  49. - we can move left and right
  50. - then choose where to go down
  51.  
  52. So we use DP.
  53.  
  54. cur[c] =
  55. best answer after processing current row and standing at column c
  56.  
  57. For every open segment, we compute:
  58. - best sweep from left
  59. - best sweep from right
  60.  
  61. Then we try dropping down into the next row.
  62. */
  63.  
  64. int maxVisitedCells(vector<string> g) {
  65.     int n = g.size();
  66.     int m = g[0].size();
  67.  
  68.     if (g[0][0] == '#' || g[n - 1][m - 1] == '#') return -1;
  69.  
  70.     const ll NEG = -(1LL << 60);
  71.  
  72.     vector<ll> cur(m, NEG), nxt(m, NEG);
  73.  
  74.     // Start cell itself counts as visited
  75.     cur[0] = 1;
  76.  
  77.     for (int r = 0; r < n; r++) {
  78.         // Last row: only need to see if target can be reached in this row
  79.         if (r == n - 1) {
  80.             ll best = NEG;
  81.             int c = 0;
  82.  
  83.             while (c < m) {
  84.                 if (g[r][c] == '#') {
  85.                     c++;
  86.                     continue;
  87.                 }
  88.  
  89.                 // Find one continuous open segment [L..R]
  90.                 int L = c;
  91.                 while (c < m && g[r][c] == '.') c++;
  92.                 int R = c - 1;
  93.  
  94.                 vector<ll> pref(R - L + 1, NEG), suff(R - L + 1, NEG);
  95.  
  96.                 // Best sweep from left
  97.                 ll run = NEG;
  98.                 for (int j = L; j <= R; j++) {
  99.                     if (cur[j] != NEG) run = max(run, cur[j] - j);
  100.                     pref[j - L] = run;
  101.                 }
  102.  
  103.                 // Best sweep from right
  104.                 run = NEG;
  105.                 for (int j = R; j >= L; j--) {
  106.                     if (cur[j] != NEG) run = max(run, cur[j] + j);
  107.                     suff[j - L] = run;
  108.                 }
  109.  
  110.                 // If destination column is inside this segment, try to reach it
  111.                 if (L <= m - 1 && m - 1 <= R) {
  112.                     ll cand = NEG;
  113.  
  114.                     if (pref[m - 1 - L] != NEG) cand = max(cand, pref[m - 1 - L] + (m - 1));
  115.                     if (suff[m - 1 - L] != NEG) cand = max(cand, suff[m - 1 - L] - (m - 1));
  116.  
  117.                     best = max(best, cand);
  118.                 }
  119.             }
  120.  
  121.             return best == NEG ? -1 : (int)best;
  122.         }
  123.  
  124.         fill(nxt.begin(), nxt.end(), NEG);
  125.  
  126.         int c = 0;
  127.         while (c < m) {
  128.             if (g[r][c] == '#') {
  129.                 c++;
  130.                 continue;
  131.             }
  132.  
  133.             // Continuous open segment [L..R]
  134.             int L = c;
  135.             while (c < m && g[r][c] == '.') c++;
  136.             int R = c - 1;
  137.  
  138.             vector<ll> pref(R - L + 1, NEG), suff(R - L + 1, NEG);
  139.  
  140.             // Best way to sweep this segment from left
  141.             ll run = NEG;
  142.             for (int j = L; j <= R; j++) {
  143.                 if (cur[j] != NEG) run = max(run, cur[j] - j);
  144.                 pref[j - L] = run;
  145.             }
  146.  
  147.             // Best way to sweep this segment from right
  148.             run = NEG;
  149.             for (int j = R; j >= L; j--) {
  150.                 if (cur[j] != NEG) run = max(run, cur[j] + j);
  151.                 suff[j - L] = run;
  152.             }
  153.  
  154.             // Try going down from each column in this segment
  155.             for (int j = L; j <= R; j++) {
  156.                 if (g[r + 1][j] == '#') continue;
  157.  
  158.                 ll best = NEG;
  159.  
  160.                 if (pref[j - L] != NEG) best = max(best, pref[j - L] + j);
  161.                 if (suff[j - L] != NEG) best = max(best, suff[j - L] - j);
  162.  
  163.                 // +1 because cell below is newly visited
  164.                 if (best != NEG) nxt[j] = max(nxt[j], best + 1);
  165.             }
  166.         }
  167.  
  168.         cur.swap(nxt);
  169.     }
  170.  
  171.     return -1;
  172. }
  173.  
  174. int main() {
  175.     vector<string> g = {
  176.         "...",
  177.         ".#.",
  178.         "..."
  179.     };
  180.  
  181.     cout << maxVisitedCells(g) << '\n';
  182.     return 0;
  183. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5
https://ideone.com/BvT2S4
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!