Submission #133973

#TimeUsernameProblemLanguageResultExecution timeMemory
133973LawlietTracks in the Snow (BOI13_tracks)C++14
86.88 / 100
2164 ms1048576 KiB
#include <bits/stdc++.h> #define MAX 4010 using namespace std; typedef pair<int,int> pii; int dx[] = {0 , 0 , 1 , -1}; int dy[] = {1 , -1 , 0 , 0}; int n, m; int curNode; int node[MAX][MAX]; int dist[MAX*MAX]; bool marc[MAX][MAX]; bool marcBFS[MAX*MAX]; pii cell[MAX*MAX]; char v[MAX][MAX]; //vector<int> dist; //vector<bool> marcBFS; //vector<pii> cell; queue<int> q; bool check(int i, int j) { if(i <= 0 || j <= 0) return false; if(i > n || j > m) return false; return true; } void DFS(int i, int j)//ESTOU PEGANDO TODOS COM V { marc[i][j] = true; for(int g = 0 ; g < 4 ; g++) { int ni = i + dx[g]; int nj = j + dy[g]; if(!check(ni , nj)) continue; if(marc[ni][nj]) continue; if(v[ni][nj] != v[i][j]) continue; node[ni][nj] = node[i][j]; DFS(ni , nj); } } void DFSMake(int i, int j) { marc[i][j] = true; for(int g = 0 ; g < 4 ; g++) { int ni = i + dx[g]; int nj = j + dy[g]; //printf("%d %d %d %d\n",i,j,ni,nj); if(!check(ni , nj)) continue; //printf("i = %d %d %d %d\n",i,j,ni,nj); if(marc[ni][nj]) continue; //printf("i = %d j = %d ni = %d nj = %d\n",i,j,ni,nj); if(v[ni][nj] == '.') continue; if(v[ni][nj] != v[i][j] && !marcBFS[ node[ni][nj] ]) { if(!marcBFS[ node[ni][nj] ]) { q.push( node[ni][nj] ); marcBFS[ node[ni][nj] ] = true; dist[ node[ni][nj] ] = dist[ node[i][j] ] + 1; } //printf("i = %d j = %d %d %d\n",i,j,ni,nj); continue; } if(v[ni][nj] != v[i][j]) continue; DFSMake(ni , nj); } } int main() { scanf("%d %d",&n,&m); for(int g = 1 ; g <= n ; g++) for(int h = 1 ; h <= m ; h++) scanf(" %c",&v[g][h]); for(int g = 1 ; g <= n ; g++) { for(int h = 1 ; h <= m ; h++) { if(marc[g][h]) continue; if(v[g][h] == '.') continue; node[g][h] = curNode++;//CURNODE N EXISTE //printf("g = %d h = %d %d\n",g,h,curNode - 1) ; //dist.push_back( 0 ); cell[curNode - 1] = {g , h}; //cell.push_back({g , h}); //marcBFS.push_back(false); DFS(g , h); } } memset(marc , false , sizeof(marc)); marcBFS[0] = true; q.push(0); while( !q.empty() ) { int cur = q.front(); q.pop(); int i = cell[cur].first; int j = cell[cur].second; DFSMake(i , j); } int ans = 0; for(int g = 0 ; g < curNode ; g++) ans = max(ans , dist[g]); printf("%d\n",ans + 1); }

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
tracks.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&v[g][h]);
    ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...