제출 #101484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101484		jamielim	Tracks in the Snow (BOI13_tracks)	C++14	20.83 / 100	2114 ms	1049600 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

set<int> adj[16000000];
vector<int> topo;
int vis[16000000];

void dfs(int x){
    if(vis[x])return;
    vis[x]=1;
    for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
        if(vis[(*it)])continue;
        dfs(*it);
    }
    topo.push_back(x);
}

int main(){
    int h,w;
    scanf("%d%d",&h,&w);
    char grid[h+5][w+5];
    for(int i=0;i<h;i++){
        scanf("%s",grid[i]);
    }
    queue<pair<int,int> > q;
    int com[h][w];
    memset(com,-1,sizeof(com));
    int c=0;
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(com[i][j]==-1){
                q.push(make_pair(i,j));
                com[i][j]=c;
                while(!q.empty()){
                    pair<int,int> cur=q.front();q.pop();
                    for(int k=0;k<4;k++){
                        int nx=cur.first+dx[k],ny=cur.second+dy[k];
                        if(nx<0||ny<0||nx>=h||ny>=w)continue;
                        if(grid[nx][ny]==grid[cur.first][cur.second]&&com[nx][ny]==-1){
                            com[nx][ny]=c;
                            q.push(make_pair(nx,ny));
                        }
                    }
                }
                c++;
            }
        }
    }
    q.push(make_pair(0,0));
    while(!q.empty()){
        pair<int,int> cur=q.front();q.pop();
        ///printf("%d %d\n",cur.first,cur.second);
        if(grid[cur.first][cur.second]=='~')continue;
        for(int i=0;i<4;i++){
            int nx=cur.first+dx[i],ny=cur.second+dy[i];
            if(0<=nx&&nx<h&&0<=ny&&ny<w){
                if(grid[nx][ny]=='~')continue;
                if(grid[nx][ny]=='.'){
                    adj[com[cur.first][cur.second]].insert(com[nx][ny]);
                    continue;
                }
                if(grid[nx][ny]==grid[cur.first][cur.second]){
                    q.push(make_pair(nx,ny));
                    continue;
                }
                ///printf("%d %d %d %d\n",cur.first,cur.second,nx,ny);
                adj[com[cur.first][cur.second]].insert(com[nx][ny]);
                q.push(make_pair(nx,ny));
            }
        }
        grid[cur.first][cur.second]='~';
    }
    dfs(0);
    reverse(topo.begin(),topo.end());
    int dist[c]; memset(dist,-1,sizeof(dist));
    dist[0]=0;
    for(int i=0;i<c;i++){
        int x=topo[i];
        for(set<int>::iterator it=adj[x].begin();it!=adj[x].end();++it){
            dist[(*it)]=max(dist[(*it)],dist[x]+1);
        }
    }
    int ans=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(grid[i][j]=='.')ans=max(ans,dist[com[i][j]]);
        }
    }
    printf("%d",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

tracks.cpp: In function 'int main()':
tracks.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&w);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",grid[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 17.5 / 70