글 읽기 - 이 문제에서 어떻게 시간초과가...

sambongdj 6년 전 0

다익스트라로 가장 짧은 거리의 정점을 찾아나가는 코드를 짰는데..

어떻게 시간초과가 날 수 있쬬..;';

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define INF 987654321

const int dz[6] = {1,-1,0,0,0,0};
const int dy[6] = {0,0,1,-1,0,0};
const int dx[6] = {0,0,0,0,1,-1};

int l,r,c;

int main(){
    while(1){
        cin >> l >> r >> c;
        if(!l&&!r&&!c) break;
        pair<int,int> map[35][35][35];
        int start[3], end[3];
        for(int k=0;k<l;k++)
            for(int i=0;i<r;i++){
                string a;
                cin >> a;
                for(int j=0;j<c;j++){
                    if(a[j]=='S') {
                        map[k][i][j]=make_pair(1,INF);
                        start[0]=k; start[1]=i; start[2]=j;
                    }
                    if(a[j]=='E'){
                        map[k][i][j]=make_pair(1,INF);
                        end[0]=k; end[1]=i; end[2]=j;
                    }
                    if(a[j]=='#') map[k][i][j]=make_pair(0,INF);
                    if(a[j]=='.') map[k][i][j]=make_pair(1,INF);
                }
            }
        bool visited[35][35][35];
        for(int k=0;k<l;k++)
            for(int i=0;i<r;i++)
                for(int j=0;j<c;j++)
                    visited[k][i][j] = false;
        map[start[0]][start[1]][start[2]].second=0;
        while(1){
            int closest = INF;
            int z,y,x;
            for(int k=0;k<l;k++)
                for(int i=0;i<r;i++)
                    for(int j=0;j<c;j++)
                        if(map[k][i][j].first&&map[k][i][j].second<closest&&visited[k][i][j]==false){
                            z=k; y=i; x=j;
                            closest = map[k][i][j].second;
                        }
            if(closest==INF) break;
            if(z==l-1&&y==r-1&&x==c-1) break;
            visited[z][y][x]=true;
            for(int i=0;i<6;i++){
                int nz=z+dz[i],ny=y+dy[i],nx=x+dx[i];
                if(nz<0||nz>=l||ny<0||ny>=r||nx<0||nx>=c) continue;
                if(visited[nz][ny][nx]==true || !map[nz][ny][nx].first) continue;
                map[nz][ny][nx].second = closest+1;
            }
        }
        int res=map[end[0]][end[1]][end[2]].second;
        if(res==INF) cout << "Trapped!" << endl;
        else cout << "Escaped in " << res << " minute(s)." << endl;
    }
}
            
        
                        

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제에서 어떻게 시간초과가...

sambongdj 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말