思路：模拟

考虑起点为$(1,1)$，其实可以构建一个固定的路径

如果当前在偶数行，就往左走，如果在奇数行，就往右走（因为起始点为奇数行）

然后走到每一行的末尾，需要往下走一格，整个路径就形成一个蛇字形。

时间复杂度

$O(n\times m)$

c++代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    cout << "1 1\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < m; ++j)
            if (i & 1) {
                cout << "A";
            } else {
                cout << "D";
            }
        if (i != n - 1) {
            cout << "S";
        }
    }
    cout << "\n";
    return 0;
}

python代码

n, m = map(int, input().split())

# 起点为 (1,1)
print("1 1")

for i in range(n):
    for j in range(1, m):
        if i % 2 == 1:
            # 在偶数行，是向右的
            print("A", end="")
        else:
            # 在奇数行，是向左的
            print("D", end="")
    if i != n - 1:
        # 如果不在最后一行，那就要继续往下一行走
        print("S", end="")

print()

Java代码

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 起点为 (1,1)
        System.out.println("1 1");

        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if ((i & 1) == 1) {
                    // 在偶数行，是向右的
                    System.out.print("A");
                } else {
                    // 在奇数行，是向左的
                    System.out.print("D");
                }
            }
            if (i != n - 1) {
                // 如果不在最后一行，那就要继续往下一行走
                System.out.print("S");
            }
        }

        System.out.println();
    }
}

题目内容

小红有一些宝物藏在了家里的地板下面，地板为一个一个方格。现在他忘了有多少宝物,也忘了存放的位置。他现在希望你从一个点出发，翻开所有的地板一次且仅有一次。现在想让你找出翻开的路径。

输入描述

两个正整数$n$和$m$，用空格隔开表示家中地板的大小

$1 \leq n,m \leq 1000$

保证$n$，$m$不同时为$1$

输出描述

第一行输入两个正整数$x$和$y$，代表初始的点为第$x$行第$y$列

第二行输入一个长度为$n*m-1$的字符串，共有$4$种字符；

"$W$"向上走

"$S$"向下走

"$A$"向左走

"$D$"向右走

有多解时输出任意即可。

样例

输入

3 3

输出

3 1
DWAWDDSS

说明

如以下顺序所示