solution.md

# 最优路线

**题目描述**

探险队要穿越泥潭，必须选择可踩踏的落脚点。可是泥潭面积很大，落脚点又实在少得可怜，一不小心就会深陷泥潭而无法脱身。侦查员费尽周折才从老乡手里弄到了一份地图，图中标出了落脚点的位置，而且令人震惊的是：泥潭只有一条穿越路线，且对于 n×m 的地图，路线长度为 n+m-1！请编程为探险队找出穿越路线。

**输入描述**

两个整数 n 和 m，表示泥潭的长和宽。下面 n 行 m 列表示地形（0 表示泥潭，1 表示落脚点）

**输出描述**

用坐标表示穿越路线，坐标之间用 > 分隔

**样例输入**

```json
6 9
1 1 1 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1
```

**样例输出**

```json
(1,1)>(1,2)>(1,3)>(2,3)>(2,4)>(2,5)>(3,5)>(4,5)>(4,6)>(5,6)>(5,7)>(5,8)>(5,9)>(6,9)
```

以下程序实现了这一功能，请你填补空白处的内容：

```cpp
#include <stdio.h>
#include <string.h>
const int N = 101;
int map[N][N];
int n, m;
struct point
{
    int l, r;
} node[N];
int ans;
void DFS(int x, int y)
{
    if (x == n && y == m)
    {
        for (int i = 1; i < ans; i++)
            printf("(%d,%d)>", node[i].l, node[i].r);
        printf("(%d,%d)\n", x, y);
    }
    else
    {
        if (map[x][y] == 1 && x <= n && y <= m)
        {
            node[ans].l = x;
            node[ans].r = y;
            ans++;
            DFS(x + 1, y);
            DFS(x, y + 1);
        }
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        ans = 1;
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &map[i][j]);
        DFS(1, 1);
    }
    return 0;
}
```

## template

```cpp
#include <stdio.h>
#include <string.h>
const int N = 101;
int map[N][N];
int n, m;
struct point
{
    int l, r;
} node[N];
int ans;
void DFS(int x, int y)
{
    if (x == n && y == m)
    {
        for (int i = 1; i < ans; i++)
            printf("(%d,%d)>", node[i].l, node[i].r);
        printf("(%d,%d)\n", x, y);
    }
    else
    {
        if (map[x][y] == 1 && x <= n && y <= m)
        {
            node[ans].l = x;
            node[ans].r = y;
            ans++;
            DFS(x + 1, y);
            DFS(x, y + 1);
        }
    }
}
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        ans = 1;
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &map[i][j]);
        DFS(1, 1);
    }
    return 0;
}
```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```