fork download
copy 
  1. #include<bits/stdc++.h>                                                //
  2. using namespace std;                                                   //
  3. #define ll long long                                                   //
  4. #define all(x, y) (x).begin() + 1, (x).begin() + (y) + 1               //
  5. #define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0) //
  6. #define el cerr<<'\n';                                                 //
  7. #define yes cout<<"YES\n"                                              //
  8. #define nah cout<<"NO\n"                                               //
  9. #define debug(x) cerr << #x << " = " << x << '\n'                      //
  10. #define sevpts main                                                    //
  11. #define vl vector<ll>                                                  //
  12. #define pii pair<ll, ll>                                               //
  13. #define FOR(i,a,b)  for (int i=a; i<=b; ++i)                           //
  14. #define FORD(i,a,b) for (int i=a; i>=b; --i)                           //
  15. #define pb push_back                                                   //
  16. #define fi first//                               __                    //
  17. #define se second//                            <(o )____               //
  18. const ll MOD2 = 988244353;//                    (  ._> /               //
  19. const ll MOD = 1e9 + 7;//                        `----'                //
  20. const long long INF = 2 * 1e18;                                        //
  21. const ll maxn = 5e5 + 69;                                              //
  22. const ll maxn2 = 1e3 + 69;                                             //
  23. //_____________________________________________________________________//
  24. ll n,  m;
  25. #define vcl vector< vector< vl > >
  26. int dx[10] = {-1, 1, 0, 0};
  27. int dy[10] = {0, 0, -1, 1};
  28. vcl mat(105, vector< vl > (105, vl (2)));
  29. bool valid(ll y, ll x, ll y1, ll x1, ll P, ll C, ll Z, ll N) {
  30.     bool flag1 = (1<=y1 && y1<=n && 1<=x1 && x1 <= m);
  31.     if(!flag1) return false;
  32.     ll x_offset = x1-x, y_offset = y1-y;
  33.  
  34.     ll side = (x_offset!=0);
  35.     y_offset = -(y_offset < 0);
  36.     x_offset = -(x_offset < 0);
  37.     ll door_color = mat[y+y_offset][x+x_offset][side];
  38.     bool flag2 = (door_color == P|| door_color == C*2|| door_color == Z*3|| door_color == N*4);
  39.     return flag2;
  40. }
  41.  
  42. vector< vl > vis(105, vl ( 105, 0 ));
  43. ll ans = 0;
  44. bool stop = false;
  45. void dfs(ll y, ll x, ll end_y, ll end_x, ll P, ll C, ll Z, ll N) {
  46.     vis[y][x] = true;
  47.     if(x == end_x && y == end_y) {
  48.         ans = 1;
  49.         stop = true;
  50.     }
  51.     else{
  52.         FOR(i,0,3){
  53.             if(stop) break;
  54.             ll x1 = x + dx[i], y1 = y + dy[i];
  55.             if(valid(y,x,y1,x1, P, C, Z, N) && !vis[y1][x1]) {
  56.                 dfs(y1,x1,end_y,end_x, P, C, Z, N);
  57.             }
  58.         }
  59.     }
  60. }
  61. int cur[4];
  62. bool ok = 0;
  63. void quaytay(ll a,ll b,ll c,ll d,ll pos, ll num) {
  64.     if(pos > 3 ) {
  65.         ans = 0;
  66.         stop = false;
  67.         FOR(i,1,n) FOR(j,1,m) vis[i][j] = 0;
  68.         dfs(a,b,c,d, cur[0], cur[1], cur[2], cur[3]);
  69.         if(ans) ok =  1;
  70.     }
  71.     else {
  72.         if(num > 0) {
  73.             cur[pos] = 1;
  74.             quaytay(a,b,c,d,pos+1,num-1);
  75.         }
  76.         cur[pos] = 0;
  77.         quaytay(a,b,c,d,pos+1,num);
  78.  
  79.     }
  80. }
  81. ll calc(ll y, ll x, ll y1, ll x1){
  82.     // xet TH i mau duy nhat:
  83.     FOR(i,1,3) {
  84.         FOR(j,0,3) cur[j] = 0;
  85.         ok = 0;
  86.         quaytay(y,x,y1,x1,0,i);
  87.         // debug(i);
  88.         // debug(ok);
  89.         // el;
  90.         if(ok) return i;
  91.     }
  92.     return 4;
  93.  
  94. }
  95.  
  96.  
  97. void sol() {
  98.     // P:1 C:2 Z:3 N:4
  99.     //mat[i][j][1] = ngang[i][j];
  100.     //mat[i][j][0] = doc[i][j];
  101.  
  102.     cin >> n >> m;
  103.     string s;
  104.     FOR(i,1,n) {
  105.         cin>> s;
  106.         FOR(j,0,s.size()-1) {
  107.             ll val = 4;
  108.             if(s[j] == 'P') val = 1;
  109.             if(s[j] == 'C') val = 2;
  110.             if(s[j] == 'Z') val = 3;
  111.             mat[i][j+1][1] = val;//ngang
  112.         }
  113.     }
  114.     FOR(i,1,n-1) {
  115.         cin>> s;
  116.         FOR(j,0,s.size()-1) {
  117.             ll val = 4;
  118.             if(s[j] == 'P') val = 1;
  119.             if(s[j] == 'C') val = 2;
  120.             if(s[j] == 'Z') val = 3;
  121.             mat[i][j+1][0] = val;//doc
  122.         }
  123.     }
  124.  
  125.     ll q;
  126.     cin>>q;
  127.     while(q--) {
  128.         vis = vector<vl>(105, vl(105, 0));
  129.         ll a,b,c,d;
  130.         cin >> a >> b >> c >> d;
  131.         cout<<calc(a,b,c,d)<<'\n';
  132.     }
  133. }
  134.  
  135. signed sevpts(){
  136.     fast;
  137.     ll tt = 1;
  138.     //cin >> tt;
  139.     while(tt--)
  140.     sol();
  141.     return 0;
  142. }
  143.  
  144.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/a9NRBc
language:
C++14 (gcc 8.3)
created:
12 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!