Submission #1152533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152533		s_sadullayev	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	664 ms	43056 KiB

tracks

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
vector<string>a(4005);
vector<vector<bool>>used(4005,vector<bool>(4005));
vector<int>dx={0,0,-1,1};
vector<int>dy={-1,1,0,0};
int cnt=0;
void bfs(queue<pair<int,int>>&q1, queue<pair<int,int>>&q2){
    if(q1.empty()) return;
    ++cnt;
    while(!q1.empty()){
        int x=q1.front().first;
        int y=q1.front().second;
        q1.pop();
        for(int i=0; i<4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m || a[nx][ny]=='.' || used[nx][ny]) continue;
            used[nx][ny] = true;
            if(a[nx][ny] != a[x][y])  q2.push(make_pair(nx, ny));
            else q1.push(make_pair(nx, ny));
        }
    }
    bfs(q2,q1);
}
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i];
 
    queue<pair<int,int>> q1,q2;
    q1.push(make_pair(0, 0));
    
    used[0][0] = true;
    bfs(q1,q2);
    cout<<cnt;
}

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