Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <sstream>
- #include <string>
- #include <iostream>
- #include <limits>
- #include <stdexcept>
- #include <unordered_set>
- #include <unordered_map>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cstdlib>
- #include <numeric>
- #include <array>
- #include <iomanip> // std::setprecision
- #include <tuple>
- #include <iostream>
- #include <fstream>
- using namespace std;
- #define int int64_t
- int32_t main(){ //== Move the King
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- /*
- https://codeforces.com/group/rMBUcNF3gx/contest/413498/problem/B
- Permutations
- DP Games
- DP Regular
- Exchange argument (Narrow down the answer)
- Combinatorics
- 3 3
- ...
- ...
- .X.
- */
- //== Move the King === :))))) Love this problem
- int n, m;
- cin >> n >> m;
- vector<vector<char>> board (n, vector<char>(m, ' ')) ;
- vector<vector<int>> dp(n, vector<int>(m, 0)); //== how to initialize first_player / second_player states ?? depend on who plays the first hand ???
- for(int row = 0; row < n; ++row) { //== do I need to hash the row+col to identify the cell's position ?
- /*
- First one to move the king to a special cell wins. One who can not make a move, loses.
- Define who wins if both player are playing optimally.
- //== did NOT say which player will play the first round ???? == "First play" will play the 1st round
- */
- for ( int col = 0; col < m; ++col) {
- char c;
- cin >> c;
- board[row][col] = c;
- }
- }
- //dp[n-1][m-1] = 0;
- for ( int row = n-1; row >= 0; --row) {
- for ( int col = m-1; col >= 0; --col){
- if (board[row][col] == 'X') {
- continue;
- }
- if( row+1 < n && !dp[row+1][col]) {
- dp[row][col] = 1;
- }
- if (col+1 < m && !dp[row][col+1]) {
- dp[row][col] = 1;
- }
- if (row+1 < n && col+1 < m && !dp[row+1][col+1]) {
- dp[row][col] = 1;
- }
- }
- }
- if( dp[0][0] == 1) {
- cout <<"First";
- } else {
- cout <<"Second";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment