글 읽기 - TLE

toastifishi 4년 전 0

Y TLE?? ):

#include <stdio.h>
#include <string.h>
using namespace std;
struct _queue {
    int y;
    int x;
    int cnt;
};
_queue q[1000000+5];
char g[1000+5][1000+5];
int vt[1000+5][1000+5];
int n, m;
int t;
int _max = -0x7fffffff;
int dy[4] = {1, 0, -1, 0}, dx[4] = {0, 1, 0, -1};
void input() {
    scanf("%d %d", &m, &n);
    for(int i = 0; i < n; i++) {
        scanf("%s", &g[i]);
    }
}
int bfs(int sy, int sx) {
    int r = 0;
    int f = 0;
    _queue k;
    q[r++] = {sy, sx, 0};
    do {
        k = q[f++];
        for(int i = 0; i < 4; i++) {
            int ny = k.y + dy[i];
            int nx = k.x + dx[i];
            if(vt[ny][nx] == 0 && g[ny][nx] == '.') {
                vt[ny][nx] = 1;
                q[r++] = {ny, nx, k.cnt+1};
            }
        }
    } while(f != r);
    return q[f-1].cnt;
}
void _search() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(g[i][j] == '.') {
                int t = bfs(i, j);
                if(t > _max) {
                    _max = t;
                }
                memset(vt, 0, sizeof(vt));
            }
        }
    }
    printf("Maximum rope length is %d.\n", _max);
    _max = -0x7fffffff;
}
int main() {
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        input();
        _search();
    }
    return 0;
}

cheetose 4년 전 0

모든 점에 대해 bfs를 돌리면 시간복잡도는 O(C²R²)입니다.

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

문제

문제

출처

ICPC

TLE

toastifishi 4년 전 0

cheetose 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말