fork download
copy 
  1. /*
  2. Problem: Walking through a grid following the pattern R -> B -> I -> K -> R -> ...
  3.  
  4. You start at any 'R' cell and can move up/down/left/right, but only to cells 
  5. that have the next letter in the sequence (R needs B, B needs I, I needs K, K needs R).
  6.  
  7. Scoring: Each time you complete a full RBIK cycle (stepping from K to R), you earn 1 point.
  8.  
  9. Output: 
  10. - "infinity" if you can loop forever
  11. - Otherwise, the maximum points you can possibly earn
  12.  
  13. ==================================================================================
  14. HOW WE SOLVE THIS:
  15. ==================================================================================
  16.  
  17. Think of this grid as a maze where you can only move to specific neighbors.
  18.  
  19. STEP 1: Build a map of legal moves
  20. - Look at each cell and figure out where you can go from there
  21. - From an 'R' cell, you can only move to neighboring 'B' cells
  22. - From a 'B' cell, you can only move to neighboring 'I' cells
  23. - From an 'I' cell, you can only move to neighboring 'K' cells
  24. - From a 'K' cell, you can only move to neighboring 'R' cells (and score a point!)
  25.  
  26. STEP 2: Can we walk in circles forever?
  27. - Imagine you're walking through the grid following the rules
  28. - If you ever come back to a cell you've already visited, you found a loop!
  29. - If there's a loop, you can walk around it forever, scoring points each time
  30. - So we check: is there any loop we can reach from a starting 'R'?
  31. - If yes → answer is "infinity"
  32.  
  33. STEP 3: Find the best path (if there's no loop)
  34. - Since there's no loop, every path must eventually end
  35. - We want to find the path that scores the most points
  36. - We use a smart technique: process cells in an order where we always know
  37.   the best way to reach each cell before we try to move past it
  38. - This is called "topological sort" - it's like processing tasks where some
  39.   tasks must be done before others
  40.  
  41. Example walkthrough:
  42. Grid:    R B
  43.          K I
  44.  
  45. From R(0,0): can go to B(0,1) → score so far: 0
  46. From B(0,1): can go to I(1,1) → score so far: 0  
  47. From I(1,1): can go to K(1,0) → score so far: 0
  48. From K(1,0): can go back to R(0,0) → score +1 point! Total: 1
  49.  
  50. But wait! We're back at R(0,0) which we visited before → that's a loop!
  51. So the answer would be "infinity" for this grid.
  52.  
  53. Time it takes: We visit each cell a few times, so it's fast even for big grids
  54. Memory needed: We store information about each cell and its connections
  55. ==================================================================================
  56. */
  57.  
  58. #include <bits/stdc++.h>
  59. using namespace std;
  60.  
  61. // Given a letter, what comes next in the R-B-I-K sequence?
  62. char get_next(char c) {
  63.     if (c == 'R') return 'B';
  64.     if (c == 'B') return 'I';
  65.     if (c == 'I') return 'K';
  66.     return 'R';  // K wraps back to R (and we score a point!)
  67. }
  68.  
  69. int main() {
  70.     ios::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.  
  73.     int rows, cols;
  74.     cin >> rows >> cols;
  75.  
  76.     vector<string> grid(rows);
  77.     for (int i = 0; i < rows; i++) {
  78.         cin >> grid[i];
  79.     }
  80.  
  81.     int num_cells = rows * cols;
  82.  
  83.     // We'll treat the grid as one long list of cells
  84.     // This helper converts a (row, col) position to a single cell number
  85.     auto get_id = [&](int r, int c) { 
  86.         return r * cols + c; 
  87.     };
  88.  
  89.     // =============================================================================
  90.     // STEP 1: Build a map of where we can move
  91.     // =============================================================================
  92.  
  93.     // graph[i] = list of cells we can reach from cell i
  94.     vector<vector<int>> graph(num_cells);
  95.  
  96.     // Keep track of all 'R' cells because those are our starting points
  97.     vector<int> start_positions;
  98.  
  99.     // Look at every cell in the grid
  100.     for (int r = 0; r < rows; r++) {
  101.         for (int c = 0; c < cols; c++) {
  102.             char letter = grid[r][c];
  103.  
  104.             // If this is an 'R', we can start here
  105.             if (letter == 'R') {
  106.                 start_positions.push_back(get_id(r, c));
  107.             }
  108.  
  109.             // What letter are we looking for in the next cell?
  110.             char next_needed = get_next(letter);
  111.  
  112.             // Check all 4 directions: up, down, left, right
  113.             int dr[] = {-1, 1, 0, 0};
  114.             int dc[] = {0, 0, -1, 1};
  115.  
  116.             int my_id = get_id(r, c);
  117.  
  118.             for (int d = 0; d < 4; d++) {
  119.                 int new_r = r + dr[d];
  120.                 int new_c = c + dc[d];
  121.  
  122.                 // Make sure the new position is inside the grid
  123.                 if (new_r < 0 || new_r >= rows || new_c < 0 || new_c >= cols) {
  124.                     continue;
  125.                 }
  126.  
  127.                 // Can we move there? Only if it has the letter we need
  128.                 if (grid[new_r][new_c] == next_needed) {
  129.                     graph[my_id].push_back(get_id(new_r, new_c));
  130.                 }
  131.             }
  132.         }
  133.     }
  134.  
  135.     // Now figure out which cells we can actually reach if we start from any 'R'
  136.     // We only care about these reachable cells
  137.     vector<bool> can_reach(num_cells, false);
  138.     queue<int> q;
  139.  
  140.     // Mark all starting 'R' positions as reachable
  141.     for (int start : start_positions) {
  142.         if (!can_reach[start]) {
  143.             can_reach[start] = true;
  144.             q.push(start);
  145.         }
  146.     }
  147.  
  148.     // Spread out from the starting positions, marking everything we can reach
  149.     while (!q.empty()) {
  150.         int current = q.front();
  151.         q.pop();
  152.  
  153.         // Try moving to all neighbors
  154.         for (int next : graph[current]) {
  155.             if (!can_reach[next]) {
  156.                 can_reach[next] = true;
  157.                 q.push(next);
  158.             }
  159.         }
  160.     }
  161.  
  162.     // =============================================================================
  163.     // STEP 2: Check if we can walk in circles (cycle detection)
  164.     // =============================================================================
  165.  
  166.     // We'll mark each cell with a color as we explore:
  167.     // 0 (white) = haven't visited yet
  168.     // 1 (gray) = currently exploring paths from this cell
  169.     // 2 (black) = finished exploring, no cycles found from here
  170.  
  171.     // If we ever visit a gray cell, it means we came back to where we were → cycle!
  172.  
  173.     vector<int> state(num_cells, 0);
  174.     bool has_cycle = false;
  175.  
  176.     // Check every reachable cell for cycles
  177.     for (int pos = 0; pos < num_cells && !has_cycle; pos++) {
  178.         // Skip cells we can't reach or already finished checking
  179.         if (!can_reach[pos] || state[pos] != 0) continue;
  180.  
  181.         // We'll do depth-first search without recursion
  182.         // (using a manual stack to avoid crashes on huge grids)
  183.         vector<pair<int, int>> stack;  // {current_cell, which_neighbor_to_check_next}
  184.         stack.push_back({pos, 0});
  185.         state[pos] = 1;  // Mark as gray (currently exploring)
  186.  
  187.         while (!stack.empty() && !has_cycle) {
  188.             int curr = stack.back().first;
  189.             int& neighbor_idx = stack.back().second;
  190.  
  191.             // Have we checked all neighbors of this cell?
  192.             if (neighbor_idx >= (int)graph[curr].size()) {
  193.                 state[curr] = 2;  // Mark as black (finished)
  194.                 stack.pop_back();
  195.                 continue;
  196.             }
  197.  
  198.             int next = graph[curr][neighbor_idx++];
  199.  
  200.             // Only look at cells we can reach
  201.             if (!can_reach[next]) continue;
  202.  
  203.             if (state[next] == 0) {
  204.                 // White cell - haven't visited yet, so explore it
  205.                 state[next] = 1;  // Mark as gray
  206.                 stack.push_back({next, 0});
  207.             } else if (state[next] == 1) {
  208.                 // Gray cell - we're back to a cell we're currently exploring!
  209.                 // This means we found a cycle
  210.                 has_cycle = true;
  211.             }
  212.             // If state[next] == 2 (black), we already fully explored it, so skip
  213.         }
  214.     }
  215.  
  216.     // If we found a cycle, we can loop forever and score infinite points
  217.     if (has_cycle) {
  218.         cout << "infinity\n";
  219.         return 0;
  220.     }
  221.  
  222.     // =============================================================================
  223.     // STEP 3: Find the longest path (no cycles, so there's a definite answer)
  224.     // =============================================================================
  225.  
  226.     // Strategy: process cells in "topological order"
  227.     // This means we always process a cell AFTER we've processed all the cells
  228.     // that can lead to it. This way, we know the best score to reach each cell.
  229.  
  230.     // First, count how many paths lead INTO each cell
  231.     vector<int> incoming_count(num_cells, 0);
  232.     for (int pos = 0; pos < num_cells; pos++) {
  233.         if (!can_reach[pos]) continue;
  234.  
  235.         for (int next : graph[pos]) {
  236.             if (can_reach[next]) {
  237.                 incoming_count[next]++;
  238.             }
  239.         }
  240.     }
  241.  
  242.     // Start with cells that have no incoming paths
  243.     // (these are cells we can only reach by starting there)
  244.     queue<int> process_queue;
  245.     for (int pos = 0; pos < num_cells; pos++) {
  246.         if (can_reach[pos] && incoming_count[pos] == 0) {
  247.             process_queue.push(pos);
  248.         }
  249.     }
  250.  
  251.     // For each cell, track the best score we can have when we reach it
  252.     const int IMPOSSIBLE = -1000000000;
  253.     vector<int> best_score(num_cells, IMPOSSIBLE);
  254.  
  255.     // All 'R' cells start with a score of 0
  256.     // (we haven't completed any RBIK cycles yet)
  257.     for (int start : start_positions) {
  258.         if (can_reach[start]) {
  259.             best_score[start] = 0;
  260.         }
  261.     }
  262.  
  263.     int final_answer = 0;
  264.  
  265.     // Process cells one by one in topological order
  266.     while (!process_queue.empty()) {
  267.         int current = process_queue.front();
  268.         process_queue.pop();
  269.  
  270.         // Keep track of the best score we've seen anywhere
  271.         if (best_score[current] > final_answer) {
  272.             final_answer = best_score[current];
  273.         }
  274.  
  275.         // Figure out what letter this cell has
  276.         int r = current / cols;
  277.         int c = current % cols;
  278.         char letter = grid[r][c];
  279.  
  280.         // Try moving to all neighbors
  281.         for (int next : graph[current]) {
  282.             if (!can_reach[next]) continue;
  283.  
  284.             // Do we score a point for moving from current to next?
  285.             // Yes, if we're at a 'K' moving to an 'R' (completing the cycle!)
  286.             int points = (letter == 'K') ? 1 : 0;
  287.  
  288.             // Update the neighbor's best score if we found a better path
  289.             best_score[next] = max(best_score[next], best_score[current] + points);
  290.  
  291.             // This neighbor has one less incoming path to wait for
  292.             incoming_count[next]--;
  293.  
  294.             // If we've processed all paths into this neighbor, it's ready
  295.             if (incoming_count[next] == 0) {
  296.                 process_queue.push(next);
  297.             }
  298.         }
  299.     }
  300.  
  301.     cout << final_answer << "\n";
  302.     return 0;
  303. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/mymr2R
language:
C++14 (gcc 8.3)
created:
2 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!