제출 #862593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862593		neodoomer	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	1289 ms	1048576 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pi pair<int,int>
const int N=4010;
vector<pair<pi,int> >adj[N][N];
int n,m,vis[N][N],ans;
char g[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
bool good (int i,int j)
{
    return (i>-1 && j>-1 && i<n && j<m);
}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    memset(vis,-1,sizeof vis);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(good(i,j))
            for(int d=0;d<4;d++)
            {
                int ni=i+dx[d],nj=j+dy[d];
                if(good(ni,nj))
                    adj[i][j].pb({{ni,nj},(g[i][j]!=g[ni][nj])});
            }
    deque<pi> dq;
    dq.pb({0,0});vis[0][0]=0;
    while(!dq.empty()){
        int i=dq.front().F,j=dq.front().S;
        dq.pop_front();
        for(auto p:adj[i][j])
        {
            int ni=p.F.F,nj=p.F.S,w=p.S;
            if(vis[ni][nj]!=-1)continue;
            vis[ni][nj]=w+vis[i][j];
            ans=max(ans,vis[ni][nj]);
            if(w)dq.pb({ni,nj});
            else dq.push_front({ni,nj});
        }
    }
    cout<<ans;

    return 0;
}

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