Submission #1258032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258032		motion	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	124 ms	16248 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
queue<pair<int,int>> q;
int h,w;
vector<vector<char>> grid;
vector<vector<bool>> vis;
void dfs(int x,int y,char z)
{
    if(grid[x][y]==z)
    {
        vis[x][y]=1;
    }
    else
    {
        q.push({x,y});
        return;
    }
    vector<pair<int,int>> g={{1,0},{-1,0},{0,1},{0,-1}};
    for(auto [dx,dy]:g)
    {
        int new_x=x+dx,new_y=dy+y;
        if(new_x<h && new_x>=0 && new_y<w && new_y>=0 && grid[new_x][new_y]!='.' && !vis[new_x][new_y])
        {
            dfs(new_x,new_y,z);
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin>>h>>w;
    grid=vector<vector<char>>(h,vector<char>(w));
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>grid[i][j];
        }
    }
    int ans=0;
    char curr='.';
    q.push({0,0});
    while(!q.empty())
    {
        auto [x,y]=q.front();
        q.pop();
        if(vis[x][y]==1) continue;
        if(grid[x][y]!=curr)
        {
            ans++;
            curr=grid[x][y];
        }
        dfs(x,y,curr);
    }
    cout<<ans;
}

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