牛客寒假算法基础集训营4-B-Applese 走方格

链接：​​https://ac.nowcoder.com/acm/contest/330/B​​​牛客网
 

在这个游戏中，它位于一个 n 行 m 列的方阵中的左上角（坐标为(0, 0)，行的序号为0∼n−10∼n−1，列的序号为0∼m−10∼m−1）。

现在它想不重复地走过所有格子(除了起点)，最后回到左上角的一个方案。

每次只能往上下左右其中一个方向走一格。

输入描述:

仅一行两个整数 n 和 m，表示方阵的大小。保证大于1×11×1。

输出描述:

如果存在方案，则输出一行操作，包含"L"、"R"、"U"、"D"，分别表示左、右、上、下。如果有多种方案，输出任意一种即可。
如果没有方案，则在一行中输出"-1"。

示例1

输入

2 2

输出

RDLU

示例2

输入

2 3

输出

RRDLLU

备注:

1≤n,m≤10

思路

看到这个题的时候总觉得是哪里的编程题。就是简单的数学题，但是有两个特殊的我没想到，

有以下情况：

• m=1 n=2 || n=1 m=2   这个时候就是DU || RL
• m=1 || n=1 (这种情况下是不存在的，除了上边的情况)
• m、n都为奇数时不存在
• m为偶数或者n为偶数存在

看不懂的话，在演草纸上推一下理解理解。

代码

#include<cstdio>

using namespace std;

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    if(n==1 && m==2){
        printf("RL\n");
        return 0;
    }
    if(n==2 && m==1){
        printf("DU\n");
        return 0;
    }
    if(((n&1) && (m&1)) || (n == 1 || m == 1)){
        printf("-1\n");
        return 0;
    }
    if(m%2==0){
        for(int i=0; i<n-1; i++)
            printf("D");
        printf("R");
        for(int j=1; j<m-1; j++){
            for(int i=0; i<n-2; i++){
                if(j&1){
                    printf("U");
                } else {
                    printf("D");
                }
            }
                
            printf("R");
        }
        for(int i=0; i<n-1; i++)
            printf("U");
        for(int i=0; i<m-1; i++)
            printf("L");
    } else {
        for(int i=0; i<n-1; i++)
            printf("D");
        printf("R");
        for(int i=1; i<=n; i++){
            for(int j=0; j<m-2; j++){
                if(i&1)printf("R");
                else printf("L");
            }
            if(i < n)printf("U");
        }
        printf("L");
    }
    printf("\n");
    return 0;
}