Submission #631293

#TimeUsernameProblemLanguageResultExecution timeMemory
631293czhang2718Tracks in the Snow (BOI13_tracks)C++17
95.63 / 100
2056 ms1048576 KiB
#include "bits/stdc++.h" using namespace std; const int N=4000; int n, m; short dx[]={0, 0, 1, -1}; short dy[]={1, -1, 0, 0}; vector<int> adj[N*N+1]; short grid[N][N]; int cmp[N][N]; void dfs(int u, int c){ cmp[u/m][u%m]=c; int i=u/m; int j=u%m; for(int k=0; k<4; k++){ int x=i+dx[k]; int y=j+dy[k]; if(x<0 || x==n || y<0 || y==m || grid[x][y]!=grid[i][j] || cmp[x][y]) continue; dfs(m*x+y, c); } } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ char c; cin >> c; grid[i][j]=(c=='F'?2:c=='R'?1:0); } } int c=0; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j]==0 || cmp[i][j]) continue; dfs(m*i+j, ++c); } } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j]==0) continue; for(int k=0; k<4; k++){ int x=i+dx[k]; int y=j+dy[k]; if(x<0 || x==n || y<0 || y==m || grid[x][y]==grid[i][j] || grid[x][y]==0) continue; adj[cmp[i][j]].push_back(cmp[x][y]); adj[cmp[x][y]].push_back(cmp[i][j]); } } } queue<int> q; int r=cmp[0][0]; q.push(r); vector<int> vis(c+1); for(; !q.empty(); q.pop()){ int x=q.front(); for(int k:adj[x]){ if(!vis[k] && k!=r){ vis[k]=vis[x]+1; q.push(k); } } } cout << *max_element(vis.begin(), vis.end())+1; } // when its been a long time since goodbye
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...