제출 #702085

#제출 시각아이디문제언어결과실행 시간메모리
702085luka1234Tracks in the Snow (BOI13_tracks)C++14
6.67 / 100
355 ms123400 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define ff first #define ss second #define pii pair<int,int> #define pb push_back #define epb emplace_back #define pll pair<ll,ll> using namespace std; int n,m; char c[1001][1001]; int comp[1001][1001]; bool used[1001][1001]; bool used1[1000002]; int dn[1000002]; set<int> g[1000002]; int ans=1; void dfs1(int x,int y,int ind){ used[x][y]=1; comp[x][y]=ind; for(int i=-1;i<=1;i++){ for(int j=-1;j<=1;j++){ if(i!=0&&j!=0) continue; if(i==0&&j==0) continue; if(x+i>=1&&x+i<=n&&y+j>=1&&y+j<=m){ if(used[x+i][y+j]==0&&c[x+i][y+j]==c[x][y]){ dfs1(x+i,y+j,ind); } } } } } void bfs(int das){ used1[das]=1; queue<int> q; q.push(das); dn[das]=1; while(!q.empty()){ int v=q.front(); q.pop(); for(int i:g[v]){ if(used1[i]==0){ used1[i]=1; q.push(i); dn[i]=dn[v]+1; ans=max(ans,dn[i]); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>c[i][j]; } } int ind=1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]!='*'&&used[i][j]==0){ dfs1(i,j,ind); ind++; } } } for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ int f1=comp[i][j]; int f2=comp[i][j+1]; int f3=comp[i+1][j]; if(f1!=0&&f2!=0){ g[f1].insert(f2); g[f2].insert(f1); } if(f1!=0&&f3!=0){ g[f1].insert(f3); g[f3].insert(f1); } } } bfs(1); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...