제출 #1282357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282357		Faisal_Saqib	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	519 ms	119128 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=4000;
char g[N][N];
bool vis[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int dist[N][N];
int main()
{
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dist[i][j]=1e9;
            cin>>g[i][j];
        }
    }
    deque<pair<int,int>> q;
    vis[n-1][m-1]=1;
    dist[n-1][m-1]=0;
    q.push_back({n-1,m-1});
    int ans=0;
    while(q.size())
    {
        auto it=q.front();
        q.pop_front();
        int x=it.first,y=it.second;
        // cout<<"At "<<x<<' '<<y<<' '<<dist[x][y]<<' '<<g[x][y]<<endl;
        ans=max(ans,dist[x][y]);
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            int w=(g[nx][ny]!=g[x][y]);
            if(nx>=0 and ny>=0 and nx<n and ny<m and dist[x][y]+w < dist[nx][ny] and g[nx][ny]!='.')
            {
                dist[nx][ny]=dist[x][y]+w;
                if(w)
                {
                    q.push_back({nx,ny});
                }
                else
                {
                    q.push_front({nx,ny});
                }
            }
        }
    }
    cout<<ans+1<<endl;
}

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