Submission #1120730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120730		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	270 ms	23852 KiB

tracks

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

#define ld double


const int INF = 1e18;
const int mod = 12345;
const int sz = 4e3 + 5;

int n , m , ans = 1;
char a[sz][sz];
bool vis[sz][sz];

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

bool can_go(int x , int y)
{
    if(x >= 1 && y >= 1 && n >= x && m >= y) return true;
    else return false;
}

void dfs(int i , int j , vector < pair < int , int > > &q)
{
    vis[i][j] = 1;
    for(int i = 0;i < 4;i++)
    {
        int x = i + dx[i];
        int y = j + dy[i];
        if(can_go(x , y))
        {
            if(a[x][y] == '.') continue;
            if(vis[x][y]) continue;
            if(a[i][j] != a[x][y]) q.push_back({x , y});
            else dfs(x , y , q);
        }
    }
}

int main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);
   cin >> n >> m;
   for(int i = 1;i <= n;i++)
   {
       for(int j = 1;j <= m;j++)
       {
           cin >> a[i][j];
       }
   }
   vector < pair < int , int > > q;
   vector < pair < int , int > > q2;
   dfs(1 , 1 , q);
   while(!q.empty())
   {
       ans++;
       q2.clear();
       while(!q.empty())
       {
           int x = q[q.size() - 1].first , y = q[q.size() - 1].second;
           q.pop_back();
           dfs(x , y , q2);
       }
       q = q2;
   }
   cout << ans << endl;
}

Compilation message (stderr)

tracks.cpp:7:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int INF = 1e18;
      |                 ^~~~

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