Submission #339084

#	Time	Username	Problem	Language	Result	Execution time	Memory
339084		Magi	Tracks in the Snow (BOI13_tracks)	C++14	12.08 / 100	1346 ms	644412 KiB

tracks

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

using namespace std;

int n, m, viz[NMAX+10][NMAX+10], v[NMAX+10][NMAX+10], ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
queue <pair <int, int> > Q[2], auxQ;

void init_bfs()
{   while(!auxQ.empty())
        {   pair <int, int> a = auxQ.front();
            auxQ.pop();
            for(int i=0; i<4; i++)
                {   pair <int, int> vec = {dx[i] + a.first, dy[i] + a.second};
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second] && v[vec.first][vec.second] == v[1][1])
                        {   viz[vec.first][vec.second] = 1;
                            auxQ.push(vec);
                            Q[0].push(vec);
                        }
                }
        }
}

void bfs(char ch, int t)
{   if(Q[t].empty()) return;
    ans++;
    while(!Q[t].empty())
        {   pair <int, int> a = Q[t].front();
            Q[t].pop();
            for(int i=0; i<4; i++)
                {   pair <int, int> vec = {dx[i] + a.first, dy[i] + a.second};
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second] && v[vec.first][vec.second] != '.'
                       && v[vec.first][vec.second] != ch)
                        {   viz[vec.first][vec.second] = 1;
                            Q[1-t].push(vec);
                        }
                }
        }
    if(ch == 'F') bfs('R', 1 - t);
    else bfs('F', 1 - t);
}

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];
        }
    auxQ.push({1, 1});
    Q[0].push({1, 1});
    viz[1][1] = 1;
    init_bfs();
    bfs(v[1][1], 0);
    cout << ans << '\n';
    return 0;
}

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