马里奥的油漆任务（深度优先版）

题目描述

马里奥是一位细心的油漆工人。这天他接到了一个任务：将一个 ( n ) 行 ( m ) 列的矩阵每一格都用油漆标记一个数字。

不同于常规的广度优先搜索方式，马里奥决定采用深度优先搜索的方法来标记。具体规则如下：

1. 首先标记第 1 行第 1 列的单元格，标记数字为 1；
2. 在当前位置，马里奥会按照 右、下、左、上 的优先级检查四个方向的相邻单元格：
   • 如果某个方向的单元格在矩阵范围内，并且尚未被标记，马里奥就立即移动到该单元格（而不是等本层全部标记完再处理下一步）；
   • 移动后，标记数字递增 1，然后继续从新单元格出发，重复步骤 2（即深度优先的思想）；
3. 当某个单元格所有四个方向都无法继续移动时（要么出界，要么已被标记），马里奥就回溯到上一个单元格，继续检查该单元格的剩余方向；
4. 重复以上过程，直到矩阵中所有单元格都被标记完毕。

输入格式

一行两个整数 ( n ) 和 ( m )（( 2 < n, m \le 100 )）。

输出格式

输出 ( n ) 行 ( m ) 列的标记后的矩阵，每个数字后输出一个空格（包括行末尾）。

样例

输入 3 3 输出 1 2 3 8 9 4 7 6 5

样例解释

对于 ( 3 \times 3 ) 的矩阵，标记顺序如下（编号表示标记顺序）：

过程简述：

• 从 (1,1) 开始，标记 1；
• 优先级 右： (1,2) 未标记 → 标记 2，移动到 (1,2)；
• 在 (1,2) 继续：右 (1,3) 未标记 → 标记 3，移动到 (1,3)；
• 在 (1,3)：右出界；下 (2,3) 未标记 → 标记 4，移动到 (2,3)；
• 在 (2,3)：右出界；下 (3,3) 未标记 → 标记 5，移动到 (3,3)；
• 在 (3,3)：右出界；下出界；左 (3,2) 未标记 → 标记 6，移动到 (3,2)；
• … 依此类推，直到所有格子填满。

提示

• 方向数组建议使用：int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
• 可以使用递归实现 DFS，或者用显式栈模拟回溯。
• 注意回溯时继续检查上一个格子的下一个方向。

数据范围

( 2 < n, m \le 100 )

时间限制

1 秒

内存限制

128 MB

来源

改编自广度优先搜索练习（OJ 原题 P1751）

标签

DFS，回溯，矩阵遍历