Submission #339082

#	Time	Username	Problem	Language	Result	Execution time	Memory
339082		Magi	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	155 ms	132064 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];

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

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