📝 题目大意

给定一个 $H \times W$ 的网格，每个格子上标有方向字符 U/D/L/R。从 $(1,1)$ 出发，按照格子上的方向移动，若下一步会越界则停止。如果移动过程出现循环（无限移动），输出 $-1$；否则输出最终停止的坐标。

💡 解题思路

1. 题目分析：

   • $H, W \leq 500$，网格总大小最多 $500 \times 500 = 2.5 \times 10^5$，直接模拟移动过程即可。
   • 关键在于判断是否出现循环：如果在移动过程中到达了一个已经访问过的格子，说明进入了循环，应输出 $-1$。

2. 算法推导：

   • 使用 mark[x][y] 数组记录每个格子是否被访问过。
   • 从 $(1,1)$ 开始，循环执行：
     • 若 mark[x][y] 已为 $1$（即当前格子之前来过），说明进入循环，输出 $-1$ 并结束。
     • 否则标记 mark[x][y] = 1。
     • 根据 a[x][y] 的方向尝试移动：
       • 'U'：若 $x-1 < 1$ 则越界，停止；否则 $x \leftarrow x-1$。
       • 'D'：若 $x+1 > H$ 则越界，停止；否则 $x \leftarrow x+1$。
       • 'L'：若 $y-1 < 1$ 则越界，停止；否则 $y \leftarrow y-1$。
       • 'R'：若 $y+1 > W$ 则越界，停止；否则 $y \leftarrow y+1$。
   • 当因越界而 break 时，输出当前的 $(x, y)$ 即为最终位置。

3. 边界与细节：

   • 下标从 $1$ 开始，与题目中行列编号一致。
   • 循环检测放在移动之前：如果到达一个格子时发现它已经被标记过，意味着之前以相同状态来过这里，后续必然重复之前的路径，形成无限循环。
   • 网格大小 $500 \times 500$，每个格子最多访问一次，因此模拟的步数不会超过 $2.5 \times 10^5$，$O(HW)$ 完全可行。

⏱️ 复杂度分析

• 时间复杂度：$O(HW)$，每个格子最多被访问一次。
• 空间复杂度：$O(HW)$，用于存储网格字符和访问标记数组。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10;       // 预留边界，防止越界
char a[N][N];                 // 存储网格方向字符
int mark[N][N];               // 标记访问过的格子
int h, w, x = 1, y = 1;       // 当前坐标从 (1,1) 开始

int main() {
    cin >> h >> w;
    // 读入网格
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            cin >> a[i][j];

    while (1) {
        // 如果当前格子已被访问过，说明进入循环
        if (mark[x][y]) {
            cout << -1;
            return 0;
        }
        mark[x][y] = 1;        // 标记当前格子为已访问

        // 根据方向字符尝试移动，越界则停止
        if (a[x][y] == 'U') {
            if (x - 1 < 1) break;   // 向上越界
            x--;
        }
        else if (a[x][y] == 'D') {
            if (x + 1 > h) break;   // 向下越界
            x++;
        }
        else if (a[x][y] == 'L') {
            if (y - 1 < 1) break;   // 向左越界
            y--;
        }
        else if (a[x][y] == 'R') {
            if (y + 1 > w) break;   // 向右越界
            y++;
        }
    }
    // 因越界而停止，输出最终位置
    cout << x << " " << y;
    return 0;
}