rembocoder

Untitled

May 8th, 2023
696
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <sstream>
  4. #include <string>
  5. #include <iostream>
  6. #include <limits>
  7. #include <stdexcept>
  8. #include <unordered_set>
  9. #include <unordered_map>
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <set>
  14. #include <stack>
  15. #include <queue>
  16. #include <algorithm>
  17. #include <cstdlib>
  18. #include <numeric>
  19. #include <array>
  20. #include <iomanip>      // std::setprecision
  21. #include <tuple>
  22. #include <iostream>
  23. #include <fstream>
  24.  
  25. using namespace std;
  26.  
  27. #define int int64_t
  28.  
  29. int32_t main(){ //== Move the King
  30.     ios_base::sync_with_stdio(false);
  31.     cin.tie(0); cout.tie(0);
  32.  
  33.     /*
  34.      https://codeforces.com/group/rMBUcNF3gx/contest/413498/problem/B
  35.  
  36.      Permutations
  37.      DP Games
  38.      DP Regular
  39.      Exchange argument (Narrow down the answer)
  40.      Combinatorics
  41.  
  42.  
  43.      3 3
  44.      ...
  45.      ...
  46.      .X.
  47.      */
  48.  
  49.     //== Move the King === :))))) Love this problem
  50.  
  51.     int n, m;
  52.     cin >> n >> m;
  53.     vector<vector<char>> board (n, vector<char>(m, ' ')) ;
  54.     vector<vector<int>> dp(n, vector<int>(m, 0));  //== how to initialize first_player / second_player states ?? depend on who plays the first hand ???
  55.     for(int row = 0; row < n; ++row) {  //== do I need to hash the row+col to identify the cell's position ?
  56.         /*
  57.          First one to move the king to a special cell wins. One who can not make a move, loses.
  58.  
  59.          Define who wins if both player are playing optimally.
  60.  
  61.          //== did NOT say which player will play the first round ???? == "First play" will play the 1st round
  62.  
  63.          */
  64.         for ( int col = 0; col < m; ++col) {
  65.             char c;
  66.             cin >> c;
  67.             board[row][col] = c;
  68.         }
  69.     }
  70.     //dp[n-1][m-1] = 0;
  71.     for ( int row = n-1; row >= 0; --row) {
  72.         for ( int col = m-1; col >= 0; --col){
  73.             if (board[row][col] == 'X') {
  74.                 continue;
  75.             }
  76.             if( row+1 < n && !dp[row+1][col]) {
  77.                 dp[row][col] = 1;
  78.             }
  79.             if (col+1 < m && !dp[row][col+1]) {
  80.                 dp[row][col] = 1;
  81.             }
  82.             if (row+1 < n && col+1 < m && !dp[row+1][col+1]) {
  83.                 dp[row][col] = 1;
  84.             }
  85.         }
  86.     }
  87.  
  88.     if( dp[0][0] == 1) {
  89.         cout <<"First";
  90.     } else {
  91.         cout <<"Second";
  92.     }
  93.     return 0;
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment