글 읽기 - 시간초과... BFS시작점 변경마다 memset초기화하면 안되나요?

applebuddy 4년 전 0

시간초과~~~ ㅠ.ㅠ 고수형님들의 힌트좀 받고싶습니다. 부탁드립니다. 감사합니다 ^-^

#include <iostream>
#include <queue>
#include <cmath>
#include <string.h>
#define endl "\n"
using namespace std;
typedef pair<int,int> Pair;
int Ans=0, N=0;
int po[500][500];
int chk[500][500];

int tx[] = {0,0,-1,1};
int ty[] = {-1,1,0,0};

void BFS(int x, int y){
    queue<Pair> q;
    q.push(make_pair(x,y));
    chk[x][y]=1;
    while(!q.empty()){
        int nx=q.front().first;
        int ny=q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int rx=nx+tx[i];
            int ry=ny+ty[i];
            if(rx<0 || rx>=N || ry<0 || ry>=N) continue;
            if(chk[rx][ry]!=0 || po[rx][ry]<=po[nx][ny]) continue;
            chk[rx][ry]=chk[nx][ny]+1;
            Ans=max(Ans,chk[rx][ry]);
            q.push(make_pair(rx,ry));
        }
    }
}

int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>po[i][j];
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<N; k++) memset(chk[k],0,sizeof(chk[k]));
            BFS(i,j);
        }
    }
    cout << Ans << endl;
    return 0;
}

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

문제

문제

출처

ICPC

시간초과... BFS시작점 변경마다 memset초기화하면 안되나요?

applebuddy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말