fork download 
  1. #include <bits/stdc++.h>
  2. #define sandra ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  3. #include <iostream>
  4. #define el '\n'
  5. #define ll long long
  6. long long gcd(long long a, long long b) { return (!a) ? b : gcd(b % a, a); }
  7. //complexity o(loga*b)
  8. long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
  9. using namespace std;
  10. ll n,m;
  11. vector<vector<char>>grid={};
  12. vector<vector<ll>>visited={};
  13. ll dx[]={-1,0,1,0};
  14. ll dy[]={0,1,0,-1};
  15. char direct[]={'U','R','D','L'};
  16.  
  17. bool is_in_border(ll i,ll j) {
  18.     return i>=0 && i<n && j>=0 && j<m;
  19. }
  20. bool Dfs(ll x, ll y) {
  21.     visited[x][y]=1;
  22.         pair<ll,ll>curr={x,y};
  23.         if (grid[curr.first][curr.second]=='U') {
  24.             ll next_x=curr.first-1;
  25.             ll next_y=curr.second+0;
  26.             if(!is_in_border(next_x, next_y)) {
  27.                 visited[curr.first][curr.second]=2;
  28.                 return true;
  29.                 //mark current as 2 escape
  30.             }
  31.  
  32.             else if (visited[next_x][next_y]==1) {
  33.                 //cycle detection
  34.                return false;
  35.             }
  36.  
  37.             if ( Dfs(next_x, next_y))
  38.              {
  39.                  visited[curr.first][curr.second]=2;
  40.                  return true;
  41.              }
  42.              else {
  43.             // visited[curr.first][curr.second]=3;//trapped
  44.               return false;
  45.              }
  46.          }
  47.      if (grid[curr.first][curr.second]=='R') {
  48.          ll next_x=curr.first+0;
  49.          ll next_y=curr.second+1;
  50.          if(!is_in_border(next_x, next_y)) {
  51.              visited[curr.first][curr.second]=2;
  52.              return true;
  53.          }
  54.  
  55.          if (visited[next_x][next_y]==1) {
  56.              //cycle detection
  57.             return false;
  58.          }
  59.          if ( Dfs(next_x, next_y))
  60.          {
  61.              visited[curr.first][curr.second]=2;
  62.              return true;
  63.          }
  64.          // visited[curr.first][curr.second]=3;//trapped
  65.          return false;
  66.      }
  67.      else if (grid[curr.first][curr.second]=='D') {
  68.          ll next_x=curr.first+1;
  69.          ll next_y=curr.second+0;
  70.          if(!is_in_border(next_x, next_y)) {
  71.              visited[curr.first][curr.second]=2;
  72.              return true;
  73.          }
  74.  
  75.           if (visited[next_x][next_y]==1) {
  76.              //cycle detection
  77.  
  78.              return false;
  79.          }
  80.  
  81.          if ( Dfs(next_x, next_y))
  82.          {
  83.              visited[curr.first][curr.second]=2;
  84.              return true;
  85.          }
  86.          // visited[curr.first][curr.second]=3;//trapped
  87.          return false;
  88.      }
  89.      else if (grid[curr.first][curr.second]=='L') {
  90.          ll next_x=curr.first+0;
  91.          ll next_y=curr.second-1;
  92.          if(!is_in_border(next_x, next_y)) {
  93.              visited[curr.first][curr.second]=2;
  94.              return true;
  95.          }
  96.          else if (visited[next_x][next_y]==1) {
  97.              //loop
  98.              return false;
  99.          }
  100.          if ( Dfs(next_x, next_y))
  101.          {
  102.              visited[curr.first][curr.second]=2;
  103.              return true;
  104.          }
  105.          //visited[curr.first][curr.second]=3;//trapped
  106.          return false;
  107.      }
  108.      else if (grid[curr.first][curr.second]=='?') {
  109.          //h3ml el 4 a7tmalat ll ? deh
  110.          for (int i=0;i<4;i++) {
  111.              grid[curr.first][curr.second]=direct[i];
  112.              ll next_x=curr.first+dx[i];
  113.              ll next_y=curr.second+dy[i];
  114.              if (!is_in_border(next_x, next_y)) {
  115.                  continue;
  116.              }
  117.              if (visited[next_x][next_y]==1 || !Dfs(next_x, next_y)) {
  118.                  // //cycle
  119.                  // continue;
  120.                  visited[curr.first][curr.second]=3;
  121.                  return false;
  122.              }
  123.         }
  124.         visited[curr.first][curr.second]=2;
  125.         return true;
  126.     }
  127.     return false;
  128. }
  129. void solve() {
  130.     cin>>n>>m;
  131.     grid.assign(n,vector<char>(m));
  132.     visited.assign(n,vector<ll>(m,0));
  133.     for(int i=0;i<n;i++) {
  134.         for(int j=0;j<m;j++) {
  135.             cin>>grid[i][j];
  136.         }
  137.     }
  138.     ll escaped=0;
  139.     for(int i=0;i<n;i++) {
  140.         for(int j=0;j<m;j++) {
  141.             if (visited[i][j]==0) {
  142.                 Dfs(i,j);
  143.             }
  144.         }
  145.     }
  146.     for(int i=0;i<n;i++) {
  147.         for(int j=0;j<m;j++) {
  148.             if (visited[i][j]==2) {
  149.                 escaped++;
  150.             }
  151.         }
  152.     }
  153.     ll all=n*m;
  154.     cout<<all-escaped<<el;
  155. }
  156.  
  157. signed main() {
  158.     sandra
  159. ll t=1;
  160.     cin>>t;
  161.     while(t--) {
  162.         solve();
  163.     }
  164. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/gMd64q
language:
C++ (gcc 8.3)
created:
8 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!