Submission #1336188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336188		randomguy1234	Tracks in the Snow (BOI13_tracks)	C++20	38.75 / 100	2099 ms	210392 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int maxN = 4e3+7 , mod = 1e9+7;
int n , m , a[maxN][maxN];
bool visited[maxN][maxN];
int rabit , fox , total;
int dx[] = {0 , 1 , 0 , -1};
int dy[] = {-1 , 0 , 1 , 0};
void debug()
{
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j)
            cout << a[i][j] << " ";
        cout << "\n";
    }
}
void ReadData()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        string s; cin >> s;
        for (int j = 0; j < s.size(); ++j){
            if (s[j] == '.')
                a[i][j+1] = 0;
            else if (s[j] == 'R')
                a[i][j+1] = 1 , ++rabit;
            else a[i][j+1] = 2 , ++fox;
            if (s[j] != '.') ++total;
        }
    }
}
bool validcell(int x , int y)
{
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int bfs(int start)
{
    int oppo , cnt = 1;
    if (start == 1) oppo = 2;
    else oppo = 1;
    vector<pii>del;
    del.push_back({1 , 1});
    visited[1][1] = 1;
    queue<pii>qe;
    qe.push({1 , 1});
    while(!qe.empty()){
        pii u = qe.front(); qe.pop();
        int x = u.first , y = u.second;
        for (int i = 0; i < 4; ++i){
            int x1 = x + dx[i];
            int y1 = y + dy[i];
            if (validcell(x1 , y1) && a[x1][y1] == start && !visited[x1][y1]){
                visited[x1][y1] = 1;
                qe.push({x1,y1});
                del.push_back({x1,y1});
                ++cnt;
            }
        }
    }
    for (pii i : del){
        int x = i.first , y = i.second;
        a[x][y] = oppo;
    }
    if (cnt == total)
        return -1;
    else return 0;
}
void Solve()
{
    int cnt = 0;
    while(true){
        int temp;
        if (a[1][1] == 1)
            temp = bfs(1);
        else temp = bfs(2);
        memset(visited , 0 ,sizeof(visited));
        ++cnt;
        if (temp == -1)
            break;
    }
    cout << cnt;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen("main.inp" , "r")){
        freopen("main.inp" , "r" , stdin);
        freopen("main.out" , "w" , stdout);
    }
    ReadData();
    Solve();
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("main.inp" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("main.out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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