Submission #1192836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192836		Rufat	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	177 ms	20496 KiB

tracks

/*                                                                                                                                                        
                  ,----..                                                                        ____                                        ,----..    
 ,--,     ,--,   /   /   \   .--.--.       ,----..        ,---,.    ,---,        ,---,.        ,'  , `.,-.----.                    ,---,.   /   /   \   
 |'. \   / .`|  /   .     : /  /    '.    /   /   \     ,'  .' |  .'  .' `\    ,'  .' |     ,-+-,.' _ |\    /  \           ,--,  ,'  .' |  /   .     :  
 ; \ `\ /' / ; .   /   ;.  \  :  /`. /   /   .     :  ,---.'   |,---.'     \ ,---.'   |  ,-+-. ;   , ||;   :    \        ,'_ /|,---.'   | .   /   ;.  \ 
 `. \  /  / .'.   ;   /  ` ;  |  |--`   .   /   ;.  \ |   |   .'|   |  .`\  ||   |   .' ,--.'|'   |  ;||   | .\ :   .--. |  | :|   |   .'.   ;   /  ` ; 
  \  \/  / ./ ;   |  ; \ ; |  :  ;_    .   ;   /  ` ; :   :  |-,:   : |  '  |:   :  |-,|   |  ,', |  ':.   : |: | ,'_ /| :  . |:   :  :  ;   |  ; \ ; | 
   \  \.'  /  |   :  | ; | '\  \    `. ;   |  ; \ ; | :   |  ;/||   ' '  ;  ::   |  ;/||   | /  | |  |||   |  \ : |  ' | |  . .:   |  |-,|   :  | ; | ' 
    \  ;  ;   .   |  ' ' ' : `----.   \|   :  | ; | ' |   :   .''   | ;  .  ||   :   .''   | :  | :  |,|   : .  / |  | ' |  | ||   :  ;/|.   |  ' ' ' : 
   / \  \  \  '   ;  \; /  | __ \  \  |.   |  ' ' ' : |   |  |-,|   | :  |  '|   |  |-,;   . |  ; |--' ;   | |  \ :  | | :  ' ;|   |   .''   ;  \; /  | 
  ;  /\  \  \  \   \  ',  / /  /`--'  /'   ;  \; /  | '   :  ;/|'   : | /  ; '   :  ;/||   : |  | ,    |   | ;\  \|  ; ' |  | ''   :  '   \   \  ',  /  
./__;  \  ;  \  ;   :    / '--'.     /  \   \  ',  . \|   |    \|   | '` ,/  |   |    \|   : '  |/     :   ' | \.':  | : ;  ; ||   |  |    ;   :    /   
|   : / \  \  ;  \   \ .'    `--'---'    ;   :      ; |   :   .';   :  .'    |   :   .';   | |`-'      :   : :-'  '  :  `--'   \   :  \     \   \ .'    
;   |/   \  ' |   `---`                   \   \ .'`--"|   | ,'  |   ,.'      |   | ,'  |   ;/          |   |.'    :  ,      .-./   | ,'      `---`      
`---'     `--`                             `---`      `----'    '---'        `----'    '---'           `---'       `--`----'   `----'                                                                                                                                                                           */
//Author RufatM
/*#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("inline")
#pragma GCC optimize("tree-vectorize")
#pragma GCC optimize("loop-vectorize")
#pragma GCC optimize("loop-interchange")
#pragma GCC optimize("loop-block")
#pragma GCC optimize("loop-strip-mine")
#pragma GCC optimize("loop-optimize")
#pragma GCC optimize("tree-loop-distribute-patterns")
#pragma GCC optimize("tree-loop-distribute-force")
#pragma GCC optimize("tree-loop-distribute")
#pragma GCC optimize("tree-loop-vectorize")
#pragma GCC optimize("tree-loop-ivcanon")
#pragma GCC optimize("tree-loop-ivopts")
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<bool> vb;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define mt19937_64 mt_rand(chrono::steady_clock::now().time_since_epoch().count())
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
template<typename T> bool isPrime(T n) { if (n <= 1)return false;if (n <= 3)return true;if (n % 2 == 0 || n % 3 == 0)return false;for (T i = 5;i * i <= n;i += 6)if (n % i == 0 || n % (i + 2) == 0)return false;return true; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int LOG = 21;
const long long LINF = 1e18 + 7;
const int MAXN = 1e5 + 7;
signed main(){
  fastio;
  int t=1;
  //cin >> t;
  while(t--){
    int h, w;
    cin >> h >> w;
    vs g(h);
    for(int i = 0; i < h; i++){
      cin >> g[i];
    }
    char x = g[0][0];
    bool al = true;
    for(int i = 0; i < h and al; i++){
      for(int j = 0; j < w; j++){
        if(g[i][j] != '.' and g[i][j] != x){
          al = false;
          break;
        }
      }
    }
    if(al){
      cout << 1 << endl;
      return 0;
    }
    vector<vector<bool>> v(h, vector<bool>(w, false));
    queue<pii> q;
    q.push({0,0});
    v[0][0] = true;
    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    while(!q.empty()){
      auto [i, j] = q.front();
      q.pop();
      for(int k = 0; k < 4; k++){
        int ni = i + dx[k], nj = j + dy[k];
        if(ni >= 0 and ni < h and nj >= 0 and nj < w and !v[ni][nj] and g[ni][nj] == x){
          v[ni][nj] = true;
          q.push({ni, nj});
        }
      }
    }
    cout << (v[h-1][w-1] ? 2 : 3);
  }
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70