fork download
copy 
  1. /*
  2.     Problem: Minimum and Maximum Drops Needed to Fill the First Column
  3.     Company Tag: Trilogy OA
  4.  
  5.     Problem Statement:
  6.         We are given a grid.
  7.  
  8.         '.' means empty cell.
  9.         '#' means blocked cell.
  10.  
  11.         In one move:
  12.             1. Choose a row.
  13.             2. Drop a block from the left.
  14.             3. It moves right until blocked or until the end.
  15.             4. Then it falls down until blocked or until the bottom.
  16.             5. It stops there.
  17.  
  18.         We need to fill the first column with blocks.
  19.  
  20.         Return:
  21.             minimum moves needed
  22.             maximum moves possible
  23.  
  24.     Constraints:
  25.         1 <= field.length <= 12
  26.         1 <= field[0].length <= 12
  27.         field[i][j] is either '.' or '#'
  28.         The maximum number of moves will not exceed 12.
  29.  
  30.     Simple Brute Force:
  31.         Try all possible row choices.
  32.  
  33.     Why This Works:
  34.         The grid is small.
  35.         Also, the maximum number of moves is guaranteed to be at most 12.
  36.  
  37.     Better Idea:
  38.         Use DFS with memoization.
  39.  
  40.         For every board state:
  41.             - if first column is full, return {0, 0}
  42.             - otherwise, try dropping a block in every row
  43.             - recursively calculate minimum and maximum moves
  44.  
  45.     Dry Run:
  46.         field =
  47.         [
  48.             ['.', '#'],
  49.             ['.', '.']
  50.         ]
  51.  
  52.         Minimum:
  53.             Drop in row 0 twice.
  54.  
  55.         Maximum:
  56.             Drop in row 1 once,
  57.             then row 1 again,
  58.             then row 0 once.
  59.  
  60.         Answer = [2, 3]
  61.  
  62.     Time Complexity:
  63.         O(number of reachable states * rows)
  64.  
  65.     Space Complexity:
  66.         O(number of reachable states)
  67. */
  68.  
  69. #include <bits/stdc++.h>
  70. using namespace std;
  71.  
  72. class Solution {
  73. public:
  74.     int rows;
  75.     int cols;
  76.  
  77.     const int INF = 1e9;
  78.  
  79.     unordered_map<string, pair<int, int>> memo;
  80.  
  81.     string encode(vector<vector<char>>& field) {
  82.         string state;
  83.  
  84.         for (int i = 0; i < rows; i++) {
  85.             for (int j = 0; j < cols; j++) {
  86.                 state.push_back(field[i][j]);
  87.             }
  88.         }
  89.  
  90.         return state;
  91.     }
  92.  
  93.     bool firstColumnFull(vector<vector<char>>& field) {
  94.         for (int i = 0; i < rows; i++) {
  95.             if (field[i][0] == '.') {
  96.                 return false;
  97.             }
  98.         }
  99.  
  100.         return true;
  101.     }
  102.  
  103.     vector<vector<char>> dropBlock(vector<vector<char>> field, int row) {
  104.         // If the leftmost cell is already blocked, this move changes nothing.
  105.         if (field[row][0] == '#') {
  106.             return field;
  107.         }
  108.  
  109.         int r = row;
  110.         int c = 0;
  111.  
  112.         // First, the block slides to the right.
  113.         while (c + 1 < cols && field[r][c + 1] == '.') {
  114.             c++;
  115.         }
  116.  
  117.         // Then, it falls down.
  118.         while (r + 1 < rows && field[r + 1][c] == '.') {
  119.             r++;
  120.         }
  121.  
  122.         field[r][c] = '#';
  123.  
  124.         return field;
  125.     }
  126.  
  127.     pair<int, int> dfs(vector<vector<char>>& field, int movesLeft) {
  128.         if (firstColumnFull(field)) {
  129.             return {0, 0};
  130.         }
  131.  
  132.         if (movesLeft == 0) {
  133.             return {INF, -INF};
  134.         }
  135.  
  136.         string key = encode(field) + "|" + to_string(movesLeft);
  137.  
  138.         if (memo.find(key) != memo.end()) {
  139.             return memo[key];
  140.         }
  141.  
  142.         int bestMinimum = INF;
  143.         int bestMaximum = -INF;
  144.  
  145.         string before = encode(field);
  146.  
  147.         for (int row = 0; row < rows; row++) {
  148.             vector<vector<char>> nextField = dropBlock(field, row);
  149.  
  150.             string after = encode(nextField);
  151.  
  152.             // Ignore a row choice if it does not change the board.
  153.             if (before == after) {
  154.                 continue;
  155.             }
  156.  
  157.             pair<int, int> child = dfs(nextField, movesLeft - 1);
  158.  
  159.             if (child.first != INF) {
  160.                 bestMinimum = min(bestMinimum, 1 + child.first);
  161.             }
  162.  
  163.             if (child.second != -INF) {
  164.                 bestMaximum = max(bestMaximum, 1 + child.second);
  165.             }
  166.         }
  167.  
  168.         return memo[key] = {bestMinimum, bestMaximum};
  169.     }
  170.  
  171.     vector<int> solution(vector<vector<char>> field) {
  172.         rows = field.size();
  173.         cols = field[0].size();
  174.  
  175.         pair<int, int> answer = dfs(field, 12);
  176.  
  177.         return {answer.first, answer.second};
  178.     }
  179. };
  180.  
  181. int main() {
  182.     vector<vector<char>> field = {
  183.         {'.', '#'},
  184.         {'.', '.'}
  185.     };
  186.  
  187.     Solution obj;
  188.     vector<int> answer = obj.solution(field);
  189.  
  190.     cout << answer[0] << " " << answer[1] << endl;
  191.  
  192.     return 0;
  193. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3
https://ideone.com/pa1jx5
language:
C++14 (gcc 8.3)
created:
7 hours 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!