Submission #482520

#	Time	Username	Problem	Language	Result	Execution time	Memory
482520		NightRage	Tracks in the Snow (BOI13_tracks)	C++14	32.19 / 100	60 ms	24368 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pb push_back
#define F first
#define S second
#define ii pair<ll,ll>
const long double eps=1e-16;
const ll N = 3e5 + 5, M = 3e5 + 50, LOG = 21, mod = 1000000007, INF = 1e18;
const ld EPS = 1e-16;
ll n,m;



vector<int> adj[N];
int dis[500][500];

string s[500];
bool valid(int i,int j){
    return i>=0 && i<n && j>=0 &&j <m && s[i][j]!='.';
}
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int main() {
//    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    ll tt = 1;
//    cin >>tt;
    while (tt--) {
        cin >>n >>m;
        for (int i = 0; i < n; ++i) {
            cin >>s[i];
        }

        deque<pair<int,int>>dq;
        dq.push_back({0,0});
        dis[0][0]=1;
        int ans=0;
        while (!dq.empty()){
            auto cur=dq.front();
            dq.pop_front();
            ans=max(ans,dis[cur.first][cur.second]);
            for (int i = 0; i < 4; ++i) {
                int x=cur.first+dx[i],y=cur.second+dy[i];
                if(valid(x,y) && dis[x][y]==0){
                    if(s[x][y]==s[cur.first][cur.second]){
                        dis[x][y]=dis[cur.first][cur.second];
                        dq.push_front({x,y});
                    }else{
                        dis[x][y]=dis[cur.first][cur.second]+1;
                        dq.push_back({x,y});
                    }
                }
            }
        }
        cout << ans <<endl;



    }
}

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