제출 #339092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339092		Magi	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	648 ms	174204 KiB

tracks

#include <iostream>
#include <deque>
#define NMAX 4000

using namespace std;

int n, m, viz[NMAX+10][NMAX+10], cost[NMAX+10][NMAX+10], ans;
char v[NMAX+10][NMAX+10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
deque <pair <int, int> > dq;

void bfs()
{   viz[1][1] = 1;
    while(!dq.empty())
        {   pair <int, int> a = dq.front();
            dq.pop_front();
            for(int t=0; t<4; t++)
                {   pair <int, int> vec = {dx[t] + a.first, dy[t] + a.second};
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second])
                        {   viz[vec.first][vec.second] = 1;
                            if(v[a.first][a.second] == v[vec.first][vec.second])
                                {   dq.push_front(vec);
                                    cost[vec.first][vec.second] = cost[a.first][a.second];
                                }
                            else
                                {   dq.push_back(vec);
                                    cost[vec.first][vec.second] = cost[a.first][a.second] + 1;
                                }
                        }
                }
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        {   string s;
            cin >> s;
            for(int j=0; j<m; j++)
                {   v[i][j+1] = s[j];
                    if(s[j] == '.') viz[i][j+1] = 1;
                }
        }
    dq.push_front({1, 1});
    bfs();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            ans = max(ans, cost[i][j]);
    cout << ans + 1<< '\n';
    return 0;
}

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