글 읽기 - 반례좀주십시요 ㅜㅜ

seonh4996 4년 전 0

문제보면 트리의 지름구하는 문제로 바꿀 수 있는데 해보니 안됩니다 ㅜㅜ 혹시 반례있을까요?

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

string map[51];
int dy[4] = {0,0,-1,1};
int dx[4] = {1,-1,0,0};
int N, M;
  
int bfs(int y, int x){

   vector<vector<int>> visit(51,vector<int>(51,0));
   queue<pair<int,int>> q;

    q.push({y,x});
    visit[y][x] = 1;
    int dep = 1;
    pair<int,int> cur;
    while(!q.empty()){
        pair<int, int> here = q.front(); q.pop();

        for(int i = 0; i < 4; i++){
            int next_y = here.first + dy[i];
            int next_x = here.second + dx[i];
            if(next_y >= 0 && next_y < N && next_x >= 0 && next_x < M && map[next_y][next_x] == 'L' && visit[next_y][next_x] == 0){
                visit[next_y][next_x] = visit[here.first][here.second] + 1;
                if(dep < visit[next_y][next_x]){
                    dep = visit[next_y][next_x];
                    cur = {next_y,next_x};
                }
                q.push({next_y, next_x});
            }
        }
    }

    for(int i = 0; i < 51; i++)fill(visit[i].begin(), visit[i].end(), 0);
    y = cur.first;
    x = cur.second;

    q.push({y,x});
    visit[y][x] = 1;
    dep = 1;
    while(!q.empty()){
        pair<int, int> here = q.front(); q.pop();

        for(int i = 0; i < 4; i++){
            int next_y = here.first + dy[i];
            int next_x = here.second + dx[i];
            if(next_y >= 0 && next_y < N && next_x >= 0 && next_x < M && map[next_y][next_x] == 'L' && visit[next_y][next_x] == 0){
                visit[next_y][next_x] = visit[here.first][here.second] + 1;
                if(dep < visit[next_y][next_x]){
                    dep = visit[next_y][next_x];
                }
                q.push({next_y, next_x});
            }
        }
    }
    for(int i = 0; i < 51; i++)
        for(int j = 0; j < 51; j++){
            if(visit[i][j] > 0)map[i][j] = 'W';
        }
        
    return dep-1;
}

int main(){

    cin.tie(0);
    ios_base :: sync_with_stdio(0);
    
    cin >> N >> M;

    for(int i = 0; i < N; i++)
        cin >> map[i];

    int ans = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(map[i][j] == 'L')
            ans = max(ans, bfs(i,j));
        }
    }
   cout << ans;
}

luniro 3년 전 10

저도 헤매다가 찾았습니다 트리가 아닐 수도 있어서 트리지름으로는 안 됩니다

입력:
7 7
WLLLLLW
LWLWLWW
LLLWLWW
LWWWLWW
LLLLLWW
LWWWWWW
WWWWWWW
출력:
9
정답:
10

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

문제

문제

출처

ICPC

반례좀주십시요 ㅜㅜ

seonh4996 4년 전 0

luniro 3년 전 10

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말