Submission #729275

#	Time	Username	Problem	Language	Result	Execution time	Memory
729275		BBart888	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	779 ms	178428 KiB

tracks

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include<algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>






using namespace std;


const int MAXN = 5e3 + 111;
const int MOD = 1e9 + 7;
const int N = 1e6;
using ll = long long;




int d_x[]{ 0,0,-1,1 };
int d_y[]{ 1,-1,0,0 };


int h, w;
char t[MAXN][MAXN];
int dist[MAXN][MAXN];
bool vis[MAXN][MAXN];
int ans;




void bfs(int x, int y)
{
    deque<pair<int, int>> q;

    q.push_back({ x,y });
    vis[x][y] = true;
    
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            dist[i][j] = 1e9;

    dist[0][0] = 0;


    while (!q.empty())
    {
        int curr_x = q.front().first;
        int curr_y = q.front().second;
        q.pop_front();

        
        
        for (int d = 0; d < 4; d++)
        {
            int newX = d_x[d] + curr_x;
            int newY = d_y[d] + curr_y;
            
            if (newX >= 0 && newY >= 0 && newX < h && newY < w && t[newX][newY] != '.')
            {
                int w = (t[newX][newY] != t[curr_x][curr_y]);
                if (dist[newX][newY] > dist[curr_x][curr_y] + w)
                {
                    dist[newX][newY] = dist[curr_x][curr_y] + w;
                    ans = max(dist[newX][newY], ans);
                    if (w == 1)
                        q.push_back({ newX,newY });
                    else
                        q.push_front({ newX,newY });
                }
            }

        }
    }




}










int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    

    //freopen("threesum.in", "r", stdin);
    //freopen("threesum.out", "w", stdout);



    cin >> h >> w;
    
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            cin >> t[i][j];


    bfs(0, 0);

    cout << ans + 1<<'\n';















    return 0;
}

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