제출 #1242754

#제출 시각아이디문제언어결과실행 시간메모리
1242754atharv_s_13Tracks in the Snow (BOI13_tracks)C++17
2.19 / 100
924 ms294940 KiB
#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<string>grid(4002);
int ans=0;


void floodfill(int r,int c,vector<vector<bool>>&visited,char &k)
{
    stack<pair<int,int>>q;
    q.push({r,c});
    bool mark=false;
    while(!q.empty())
    {
        r=q.top().first,c=q.top().second;
        q.pop();

        if(r<0 || c<0 || r>=n || c>=m || grid[r][c]=='.') continue;
        if(visited[r][c]) continue;
        visited[r][c]=true;

        if(k!=grid[r][c] && !mark)
        {
            ans++;
            mark=true;
        }

        q.push({r-1,c});
        q.push({r,c-1});
        q.push({r+1,c});
        q.push({r,c+1});
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 0;i<n; i++)
    {
        cin>>grid[i];
    }
    vector<vector<bool>>visited(n,vector<bool>(m,false));

    floodfill(0,0,visited,grid[0][0]);
    if(grid[0][0]!='.')
    ans++;
    
    if(grid[0][0]=='.' ||  grid[n-1][m-1]=='.') cout<<0;
    else
    cout<<ans;
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...