제출 #1094771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094771		laithalnaimi	Tracks in the Snow (BOI13_tracks)	C++17	58.85 / 100	457 ms	130944 KiB

tracks

// [ الأحزاب: 56] ﴿ إِنَّ اللَّهَ وَمَلَائِكَتَهُ يُصَلُّونَ عَلَى النَّبِيِّ ۚ يَا أَيُّهَا الَّذِينَ آمَنُوا صَلُّوا عَلَيْهِ وَسَلِّمُوا تَسْلِيمًا﴾
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <deque>
#include <iomanip> 
#define mem(a, b) memset(a, b, sizeof a);
#define db(x) cout << #x << ": " << (x) << "\n";
#define coutfloat(n,d)     cout << fixed << setprecision(d) << n << endl //#include <iomanip> 
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pss pair<string , string>
#define fv(vec) for(auto &v : vec)
#define cinv(v,n) vector<int>v(n);for(int i = 0 ; i <n ; i++)cin>>v[i];
#define cinvll(v,n) vector<ll>v(n);for(ll i = 0 ; i <n ; i++)cin>>v[i];
#define fi(n) for(int i = 0 ; i < n ; i++)
#define fj(n) for(int j = 0 ; j < n ; j++)
#define feq(n) for(int eq = 0 ; eq <= n ; eq++)
#define pb push_back
#define mp make_pair
#define ll long long 
#define ini in<int>()
#define inl in<ll>()
#define inc in<char>()
#define inb in<bool>()
#define ins in<string>()
#define test int T;cin>>T;while(T--)
#define yes  cout<<"YES\n"
#define no  cout<<"NO\n"
#define LAITH ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define file freopen("knapsack.in", "r", stdin);freopen("knapsack.out", "w", stdout);
using namespace std;
 
template <typename T>
T in() { T x; cin >> x; return x; }

int meadow[4004][4004];
string snow[4004];
int n, m , ans = 1,dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
bool chk(int x, int y){
  return (x >= 0 && x <m && y >= 0 && y < n && snow[x][y] != '.');
}
void BFS(){
  deque<pii> q;
  q.push_front({0,0});
  meadow[0][0] = 1;
  while(!q.empty()){
    pii point = q.front();
    q.pop_front();
    ans = max(ans, meadow[point.first][point.second]);
    fi(4){
      int x = point.first + dx[i], y = point.second + dy[i];
      if(chk(x, y) && !meadow[x][y])
        snow[x][y] == snow[point.first][point.second] ?
          (meadow[x][y] = meadow[point.first][point.second],q.push_front({x,y})):
          (meadow[x][y] = meadow[point.first][point.second] + 1,q.push_back({x,y}));
    }
  }
}
void solve(){
  n = ini , m = ini;
  fi(n)cin >> snow[i];
  BFS();
  cout <<ans;
}
int main() {
    LAITH;
    solve();
    return 0;
}

• Subtask 1: 21.666666666666668 / 30
• Subtask 2: 37.1875 / 70