Submission #1121394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121394		Noborita	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	567 ms	34124 KiB

tracks

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

#define forn(i, n) for( int i = 0;i < n; i ++)
#define ii pair<int, int>

const int N = 4e3;

char track[N][N];
bool vis[N][N];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n, m; cin >> n >> m;
    forn(i, n)
    {
        forn (j, m)
        {
            cin >> track[i][j];
        }
    }
    int tot = 0;
    forn(i, n)
    {
        forn(j, m)
        {
            if (track[i][j] == '.' || vis[i][j]) continue;
            vis[i][j] = 1;
            int f = track[i][j] == 'F';
            int r = track[i][j] == 'R';
            queue<ii> q;
            q.push({i, j});
            while(!q.empty())
            {
                ii cur = q.front();
                q.pop();
                forn(k, 4)
                {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if (nx <0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (vis[nx][ny]) continue;
                    f += track[nx][ny] == 'F';
                    r += track[nx][ny] == 'R';
                    q.push({nx,ny});
                    vis[nx][ny] = 1;
                }
            }
            if (f) tot ++;
            if (r) tot ++;
    
        }
    }
    cout << tot << '\n';
}

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