제출 #636667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636667		LKR__enjoyer	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1371 ms	119748 KiB

tracks

#include<bits/stdc++.h>
#include <iostream>

using namespace std;
#define f first
#define s second
int n,m;
char grid[4000][4000];
int odl[4000][4000];
int wynik=1;
pair<int,int> ruchy[4]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int i,int j)
{
deque<pair<int,int>> w; 
w.push_front({i,j});
    while(w.size())
    {
        pair<int,int> akt=w.front();
    w.pop_front();
    wynik=max(wynik,odl[akt.f][akt.s]);
        for(int z=0;z<4;z++)
        {
        int u1=akt.f+ruchy[z].f;
        int u2=akt.s+ruchy[z].s;    
            if(u1<0||u1>=n||u2<0||u2>=m||grid[u1][u2]=='.'||odl[u1][u2]!=0)continue;
            
              int waga=0;
            if(grid[akt.f][akt.s]!=grid[u1][u2])waga=1;
            odl[u1][u2]=odl[akt.f][akt.s]+waga;
            if(waga==1)w.push_back({u1,u2});
            else w.push_front({u1,u2});
                    
        }
    }
}
int main()
{  ios_base::sync_with_stdio(); cin.tie();
    cin>>n>>m;
for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
        cin>>grid[i][j];
odl[0][0]=1;
bfs(0,0);
cout<<wynik;
    return 0;
}

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