제출 #1032544

#제출 시각아이디문제언어결과실행 시간메모리
1032544hippo123Tracks in the Snow (BOI13_tracks)C++17
56.25 / 100
2131 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pr pair<ll, ll> #define f first #define s second #define pb push_back const int ndim=4001; int ns; vector<vector<int>> d(ndim, vector<int>(ndim)); map<pr, int> ms; vector<vector<bool>> vis(ndim, vector<bool>(ndim, false)); vector<set<int>> adj(2e5); int h, w; int dx[4]={1, -1, 0, 0}; int dy[4]={0, 0, 1, -1}; void dfs(int x, int y, int col, int num){ if(x<0 || x>=h || y<0 || y>=w ) return; if(d[x][y]!=col || vis[x][y]) return; //cout<<" x/y= "<<x<<" "<<y<<endl; ms[{x,y}]=num; vis[x][y]=true; for (int i=0; i<4; i++){ int xn=x+dx[i]; int yn=y+dy[i]; dfs(xn, yn, col, num); } } void dfs1(int x, int y, int col, int num){ if(x<0 || x>=h || y<0 || y>=w ) return; if(d[x][y]!=col || vis[x][y]) return; //cout<<" x/y= "<<x<<" "<<y<<endl; vis[x][y]=true; for (int i=0; i<4; i++){ int xn=x+dx[i]; int yn=y+dy[i]; if(xn<0 || xn>=h || yn<0 || yn>=w ) continue; if(d[xn][yn]==-1) continue; if(d[xn][yn]!=d[x][y]){ adj[ms[{xn, yn}]].insert(ms[{x, y}]); adj[ms[{x, y}]].insert(ms[{xn, yn}]); } dfs1(xn, yn, col, num); } } int main(){ cin>>h>>w; //vector<vector<int>> d(h, vector<int> (w, -1)); int nf=0; for (int i=0; i<h; i++){ string s; cin>>s; for (int j=0; j<w; j++){ if(s[j]=='.') { d[i][j]=-1; continue; } nf++; if(s[j]=='R') d[i][j]=0; else d[i][j]=1; } } //for (int i=0; i<h; i++){ // for (int j=0; j<w; j++) cout<<d[i][j]<<" "; // cout<<endl; //} int num=0; for (int i=0; i<h; i++){ for (int j=0; j<w; j++){ if((d[i][j]!=-1) & (!vis[i][j])) { dfs(i, j, d[i][j], num); num++; } } } //cout<<" we are here"<<endl; //============== for (int i=0; i<h; i++){ for (int j=0; j<w; j++) vis[i][j]=false; } for (int i=0; i<h; i++){ for (int j=0; j<w; j++){ if((d[i][j]!=-1) & (!vis[i][j])) { dfs1(i, j, d[i][j], num); } } } //cout<<" we are here"<<endl; //for (int i=0; i<num; i++) { // for (auto e: adj[i]) cout<<e<<" "; // cout<<endl; //} vector<bool> vis1(num, false); vector<int> level(num, -1); queue<pr> q; q.push({0, 0}); // node, lev level[0]=0; int lv_max=0; while (!q.empty()){ pr nd=q.front(); q.pop(); int node=nd.f; int lev=nd.s; for (int elem: adj[node]){ //cout<<" elem= "<<elem<<endl; if(level[elem]==-1){ level[elem]=lev+1; q.push({elem, lev+1}); lv_max=max(lv_max, lev+1); } } } cout<<lv_max+1<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...