알고리즘: 소 이 를 구하 기
3683 단어 검지 offer - 이 진 트 리
『 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;
}