fork download
copy 
  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. const ll N = 32768, MOD = 32768, INF = 1e9 + 3;
  11. ll n,m;
  12. vector<vector<char>>grid={};
  13. vector<vector<ll>>visited={};
  14. ll dx[]={-1,0,1,0};
  15. ll dy[]={0,1,0,-1};
  16. char direct[]={'U','R','D','L'};
  17.  
  18. bool is_in_border(ll i,ll j) {
  19.     return i>=0 && i<n && j>=0 && j<m;
  20. }
  21.  
  22. bool Dfs(long long next_x, long long next_y);
  23.  
  24. bool check(pair<ll,ll>curr,char dir) {
  25.     ll next_x=curr.first;
  26.     ll next_y=curr.second;
  27.     if (dir=='U') {
  28.         next_x=next_x-1;
  29.     }
  30.     else if (dir=='R') {
  31.         next_y=next_y+1;
  32.     }
  33.     else if (dir=='D') {
  34.         next_x=next_x+1;
  35.     }
  36.     else if (dir=='L') {
  37.         next_y=next_y-1;
  38.     }
  39.     if(!is_in_border(next_x, next_y)) {
  40.         visited[curr.first][curr.second]=2;
  41.         return true;
  42.         //mark current as 2 escape
  43.     }
  44.  
  45.     if (visited[next_x][next_y]==1) {
  46.         //cycle detection
  47.         return false;
  48.     }
  49.     if (visited[next_x][next_y] == 2) {
  50.         visited[curr.first][curr.second] = 2;
  51.         return true;
  52.     }
  53.     if (Dfs(next_x, next_y))
  54.     {
  55.         visited[curr.first][curr.second]=2;
  56.         return true;
  57.     }
  58.     return false;
  59. }
  60.  
  61. bool Dfs(ll x, ll y) {
  62.     visited[x][y]=1;
  63.         pair<ll,ll>curr={x,y};
  64.     char directionn=grid[x][y];
  65.  
  66.        if (grid[curr.first][curr.second]!='?') {
  67.            return check(curr,directionn);
  68.        }
  69.       if (grid[curr.first][curr.second]=='?') {
  70.          //h3ml el 4 a7tmalat ll ? deh
  71.          for (int i=0;i<4;i++) {
  72.              grid[curr.first][curr.second]=direct[i];
  73.              ll next_x=curr.first+dx[i];
  74.              ll next_y=curr.second+dy[i];
  75.              if (!is_in_border(next_x, next_y)) {
  76.                  continue;
  77.              }
  78.  
  79.              if (visited[next_x][next_y]==1 || !Dfs(next_x, next_y)) {
  80.                  // //cycle
  81.                  // continue;
  82.                  visited[curr.first][curr.second]=3;
  83.                  return false;
  84.              }
  85.         }
  86.        visited[curr.first][curr.second]=2;
  87.         return true;
  88.     }
  89.     return false;
  90. }
  91.  
  92. void solve() {
  93.     cin>>n>>m;
  94.     grid.assign(n,vector<char>(m));
  95.     visited.assign(n,vector<ll>(m,0));
  96.     for(int i=0;i<n;i++) {
  97.         for(int j=0;j<m;j++) {
  98.             cin>>grid[i][j];
  99.         }
  100.     }
  101.     ll escaped=0;
  102.     for(int i=0;i<n;i++) {
  103.         for(int j=0;j<m;j++) {
  104.             if (visited[i][j]==0) {
  105.                 Dfs(i,j);
  106.             }
  107.         }
  108.     }
  109.     for(int i=0;i<n;i++) {
  110.         for(int j=0;j<m;j++) {
  111.             if (visited[i][j]==2) {
  112.                 escaped++;
  113.             }
  114.         }
  115.     }
  116.     ll all=n*m;
  117.     cout<<all-escaped<<el;
  118. }
  119. signed main() {
  120.     sandra
  121. ll t=1;
  122.     cin>>t;
  123.     while(t--) {
  124.         solve();
  125.     }
  126. }
  127.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sufHmY
language:
C++ (gcc 8.3)
created:
7 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!