제출 #29801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29801		TAMREF	Portals (BOI14_portals)	C++11	0 / 100	13 ms	30636 KiB

portals

#include <bits/stdc++.h>
#define vc first
#define vp second
using namespace std;
typedef pair<int,int> pii;
const int mx=1005, inf=1e8;
int s,e;
int R,C;
int D[mx*mx];
vector<int> G[mx*mx];
char buf[mx][mx+8];
void input(){
    scanf("%d %d\n",&R,&C);
    for(int i=0;i<R;i++){
        int now=0, ls=-1, my;
        scanf("%s",&buf[i]);
        for(int j=0;j<C;j++){
            my=i*C+j;
            if(buf[i][j]=='S') s=my;
            else if(buf[i][j]=='C') e=my;
            if(buf[i][j]!='#'){
                if(now<=ls) now=j;
                if(j && buf[i][j-1]!='#'){
                    G[my].push_back(my-1);
                    G[my-1].push_back(my);
                }
                if(j==C-1 && now<j){
                    G[my].push_back(i*C+now);
                    G[i*C+now].push_back(my);
                }
            }else{
                ls=j;
                if(j && buf[i][j-1]!='#' && j-1>now){
                    G[my-1].push_back(i*C+now);
                    G[i*C+now].push_back(my-1);
                }
            }
        }
    }
    for(int j=0;j<C;j++){
        int now=0,ls=-1,my;
        for(int i=0;i<R;i++){
            my=i*C+j;
            if(buf[i][j]!='#'){
                if(now<=ls) now=i;
                if(i && buf[i-1][j]!='#'){
                    G[my].push_back(my-C);
                    G[my-C].push_back(my);
                }
                if(i==R-1 && now<i){
                    G[my].push_back(now*C+j);
                    G[now*C+j].push_back(my);
                }
            }else{
                ls=i;
                if(i && buf[i-1][j]!='#' && i-1>now){
                    G[my-C].push_back(now*C+j);
                    G[now*C+j].push_back(my-C);
                }
            }
        }
    }
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            sort(G[i*C+j].begin(),G[i*C+j].end());
            G[i*C+j].erase(unique(G[i*C+j].begin(),G[i*C+j].end()),G[i*C+j].end());
        }
    }
    /*
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            printf("(%d,%d) : ",i,j);
            for(int u : G[i*C+j]){
                printf("(%d,%d) ",u/C,u%C);
            }
            puts("");
        }
    }*/
    fill(D,D+R*C,inf);
}
void dijk(){
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push(pii(D[s]=0,s));
    while(!q.empty()){
        pii u = q.top(); q.pop();
        if(D[u.vp]<u.vc) continue;
        for(int k : G[u.vp]){
            if(D[k]>u.vc+1)
                q.push(pii(D[k]=u.vc+1,k));
        }
    }
}
int main(){
    input();
    dijk();
    printf("%d\n",D[e]);
}

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

portals.cpp: In function 'void input()':
portals.cpp:16:27: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1013]' [-Wformat=]
         scanf("%s",&buf[i]);
                           ^
portals.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d\n",&R,&C);
                           ^
portals.cpp:16:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&buf[i]);
                            ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30