제출 #624144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624144		lam	Tracks in the Snow (BOI13_tracks)	C++14	70.94 / 100	697 ms	144128 KiB

tracks

#include <bits/stdc++.h>
#define maxn 4010
using namespace std;

int n,m,dp[maxn][maxn],ans=1;
char a[maxn][maxn];
deque<pair<int,int>> q;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

bool in(int x, int y)
{
    if (x<1||x>n) return 0;
    if (y<1||y>n) return 0;
    return a[x][y]!='.';
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++) cin>>a[i][j],dp[i][j]=0;
    dp[1][1]=1;
    q.push_back({1,1});
    while (!q.empty())
    {
        int u=q.front().first;
        int v=q.front().second;
        ans=max(ans,dp[u][v]);
        q.pop_front();
        for (int c=0; c<4; c++)
        {
            int i=u+dx[c]; int j=v+dy[c];
            if (in(i,j)&&dp[i][j]==0)
            {
                if (a[i][j]==a[u][v]){
                    dp[i][j]=dp[u][v];
                    q.push_front({i,j});
                }
                else {
                    dp[i][j]=dp[u][v]+1;
                    q.push_back({i,j});
                }
            }
        }
    }
    cout<<ans;
}

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