알고리즘: 소 이 를 구하 기

1. 제목 설명
『 8195 』 는 1000 * 1000 의 잔디 가 있 고 샤 오 이 는 처음에 (1, 1) (가장 왼쪽 상단 의 위치) 에 서 있 었 다.샤 오 이 는 매 초 에 가로 또는 세로 로 인접 한 풀밭 으로 이동 하여 풀 을 먹는다 (샤 오 이 는 국경 을 벗 어 나 지 않 는 다).악역 들 은 귀여운 샤 오 이 를 잡 고 싶 어한 다. 그의 손 에는 n 개의 함정 이 있다.i 번 째 함정 은 가로 좌표 가 xi 이 고 세로 좌표 가 yi 인 위치 에 설치 되 어 있 으 며 샤 오 이 는 함정 에 들 어가 면 초 과 된 포착 을 당 할 것 이다.샤 오 이 를 구하 기 위해 서 는 샤 오 이 가 최소 몇 초 동안 함정 에 빠 질 수 있 는 지 알 고 샤 오 이 를 미리 구 해 야 한다.입력 설명:     첫 번 째 행위 의 정수 n (n ≤ 1000) 은 초 과 총 n 개의 함정 을 가지 고 있 음 을 나타 낸다.* 8195 ° 8195 ° 두 번 째 줄 에는 n 개의 정수 xi 가 있 는데 i 번 째 함정 의 가로 좌 표 는 8195 ° 8195 ° 세 번 째 줄 에는 n 개의 정수 yi 가 있 음 을 나타 내 고 i 번 째 함정 의 세로 좌 표 는 8195 ° 8195 ° 보증 좌 표 는 모두 잔디 범위 안에 있다 는 것 을 나타 낸다.출력 설명: 81955 ℃ 에서 하나의 정 수 를 출력 하면 최소 몇 초 만 에 초 과 된 함정 에 빠 질 수 있 음 을 나타 낸다.
2. 사고 분석
    제목 은 많은 것 을 묘 사 했 는데 요약 하면 격자 에서 왼쪽 상단 격자 에서 가장 가 까 운 격 점 을 찾 는 것 이다.이때 우 리 는 문제 의 첫 번 째 전환 을 완 성 했 고 전환 하기 전에 그렇게 이해 하기 어렵 지 않 았 다.그 다음 에 가장 가 까 운 격자 를 찾 아야 돼 요.제목 에 따 르 면 걷 는 방법 은 오른쪽으로, 아래로 만 간다.그래서 지정 격 점 까지 가 는 가장 가 까 운 노선 은 직진 이다.즉, 가장 가 까 운 노선 은 목표 격 점 횡축 의 절대 거리 와 종축 의 절대 거리의 합 이다.대 점
(Xi,Yi)
가장 가 까 운 노선 은
d=(Xi−1)+(Yi−1)=Xi+Yi−2
    그래서 모든 칸 을 옮 겨 다 니 며 d 의 가장 작은 출력 을 찾 으 면 됩 니 다.
3. C + + 구현
#include 
#include 

using namespace std;

int n;
vector<int> x, y;

int trap(int n, vector<int>& x, vector<int>& y) {
    if(x.size() != y.size() || x.empty() || y.empty() || n <= 0)
        return 0;
    int min = x[0]-1 + y[0]-1;
    for(int i = 1; i < n; i++) {
        int mid = x[i] + y[i] - 2;
        if(mid < min)
            min = mid;
    }
    return min;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        int midx;
        cin >> midx;
        x.push_back(midx);
    }
    for(int i = 0; i < n; i++) {
        int midy;
        cin >> midy;
        y.push_back(midy);
    }
    int ans = trap(n, x, y);
    cout << ans << endl;
    return 0;
}

좋은 웹페이지 즐겨찾기