Submission #490531

#	Time	Username	Problem	Language	Result	Execution time	Memory
490531		sid	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	504 ms	121604 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e17+1
ll const M = 1e5+10;
ll const N = 100001;
const int mod = 1e9+7;
ll dx[8]={1,0,-1,0,1,-1,-1,1};
ll dy[8]={0,1,0,-1,1,-1,1,-1};

ll gcd(ll a, ll b)
{
    return b==0 ? a : gcd(b,a%b);
}

int h,w;
string track[4001];
int depth[4001][4001];

int inside(int x,int y)
{
    if(x < h and x >= 0 and y < w and y >= 0 and track[x][y] != '.')return true;
    return false;
}

void solve(int t) {
    // cout << "Case #" << t << ": ";
    cin>>h>>w;
    for(int i=0;i<h;i++)
    {
        cin>>track[i];
    }
        
    depth[0][0] = 1;
    int ans = 1;
    deque<pair<int,int>> q;
    q.push_back({0,0});
    while(!q.empty())
    {
        pair<int,int> start = q.front();
        q.pop_front();
        ans = max(ans, depth[start.first][start.second]);
        for(int i=0;i<4;i++)
        {
            int x = start.first + dx[i];
            int y = start.second + dy[i];
            if(inside(x,y) and depth[x][y]==0)
            {
               if(track[x][y] == track[start.first][start.second]) {
               depth[x][y] = depth[start.first][start.second];
               q.push_front({x,y}); 
               }
               else 
               {
                depth[x][y] = depth[start.first][start.second] + 1;
                q.push_back({x,y});
               }
            } 
        } 
    }
    cout<<ans;
}
    
    int main(){
        ios_base::sync_with_stdio(false), cin.tie(nullptr);
        // #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
        // #endif
        // int T;
        // cin >> T ;
        // for(int t = 1; t <= T; t++) 
        solve(1);
    }

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