P9840 ICPC2021

N_Position · 2023-11-13 09:44:55 · 题解

题目翻译

在一个 n\times n 的地图中，每个位置都有一只袋鼠，每次操作可以使每只袋鼠整体向上下左右四个方向移动一格，袋鼠不会超出地图范围，问：如何在 3\times(n-1) 步及内将所有袋鼠移动到给定位置。

题目分析

共分为两个过程：汇集和移动到终点。

考虑汇集，显然只要所有袋鼠都在地图角落，便可汇集。

四个角中，显然要选取距离终点最近的。

最后只需要移到终点即可。

最会情况下移动到一个角上需要 2\times(n-1) 次，移动到终点最多需要 n-1 次，符合题意。

代码实现

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    if(a <= n/2){
        for(int i=1;i<n;i++){
            printf("U");
        }
        for(int i=1;i<a;i++){
            printf("D");
        }
    }else{
        for(int i=1;i<n;i++){
            printf("D");
        }
        for(int i=1;i<n-a+1;i++){
            printf("U");
        }
    }
    if(b <= n/2){
        for(int i=1;i<n;i++){
            printf("L");
        }
        for(int i=1;i<b;i++){
            printf("R");
        }
    }else{
        for(int i=1;i<n;i++){
            printf("R");
        }
        for(int i=1;i<n-b+1;i++){
            printf("L");
        }
    }
}