Submission #1270402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270402		k12_khoi	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	547 ms	119384 KiB

tracks

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

#define pii pair<int,int>
#define X first
#define Y second

const int N=4e3+5;
const int oo=1e9+1;

int n,m;
int d[N][N],dx[]={-1,0,0,1},dy[]={0,-1,1,0};
char s[N][N];
deque <pii> dq;

int bfs01(int u,int v)
{
    int x,y,w;

    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    d[i][j]=oo;

    d[u][v]=1;
    dq.push_back(make_pair(u,v));

    while (!dq.empty())
    {
        u=dq.front().X;
        v=dq.front().Y;
        dq.pop_front();

        for (int i=0;i<=3;i++)
        {
            x=u+dx[i];
            y=v+dy[i];

            if (x>0 and x<=n and y>0 and y<=m and s[x][y]!='.')
            {
                w=(s[u][v]!=s[x][y]);

                if (d[x][y]>d[u][v]+w)
                {
                    d[x][y]=d[u][v]+w;

                    if (w==0) dq.push_front(make_pair(x,y));
                    else dq.push_back(make_pair(x,y));
                }
            }
        }
    }

    return d[u][v];
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    cin >> s[i][j];

    cout << bfs01(1,1);
}

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