Submission #1326425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326425		ninstroyer	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	299 ms	78200 KiB

tracks

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

const int nx = 4e3+5;

int n,m,res=0,vis[nx][nx];
char mat[nx][nx];
vector<pair<int,int>> dir = { {1,0}, {-1,0}, {0,1}, {0,-1} };

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin>>mat[i][j];
    if(mat[1][1] == '.') return cout<<0, 0;
    char last = mat[1][1];
    char base = (last == 'R' ? 'F' : 'R');
    res = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(mat[i][j] == base)
            {
                res=2;
                break;
            }
        }
        if(res==2) break;
    }
    queue<pair<int,int>> q;
    q.push({1,1});
    vis[1][1] = 1;
    while(!q.empty())
    {
        auto [r,c] = q.front();
        q.pop();
        for(auto [rr, cc] : dir)
        {
            int dr = r+rr;
            int dc = c+cc;
            if(mat[dr][dc] == last && !vis[dr][dc])
            {
                vis[dr][dc] = 1;
                q.push({dr,dc});
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(!vis[i][j] && mat[i][j] == last)
            {
                res=3;
                break;
            }
        }
        if(res==3) break;
    }
    cout<<res;
}

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