Escape Room

题目描述

You have to determine if it is possible to escape from a room. The room is an M-by-N grid with each position (cell) containing a positive integer. The rows are numbered 1, 2, . . . , M and the columns are numbered 1, 2, . . . , N. We use (r, c) to refer to the cell in row r and column c. You start in the top-left corner at (1, 1) and exit from the bottom-right corner at (M, N). If you are in a cell containing the value x, then you can jump to any cell (a, b) satisfying a × b = x. For example, if you are in a cell containing a 6, you can jump to cell (2, 3). Note that from a cell containing a 6, there are up to four cells you can jump to: (2, 3), (3, 2), (1, 6), or (6, 1). If the room is a 5-by-6 grid, there isn’t a row 6 so only the first three jumps would be possible. 你必须确定是否有可能逃离房间。房间是一个M乘N的网格，每个位置（单元格）都包含一个正整数。行编号为 $1、2、…、，M$ 并且列被编号为 $1、2、，N$。我们使用 $（r，c）$ 来指代 $r$ 行和 $c$ 列中的单元格。从 $（1，1）$ 的左上角开始，从 $（M，N）$ 的右下角退出。如果您所在的单元格包含值 $x$，则可以跳转到满足 $a×b=x$ 的任何单元格 $（a，b）$。例如，如果您所在单元格包含 $6$，则可以跳到单元格 $（2，3）$。请注意，从一个包含6的单元格中，最多可以跳到四个单元格：$（2，3）、（3，2）、（1，6）$ 或 $（6，1）$。如果房间是 $5$ 乘 $6$ 的格子，那么就没有第 $6$ 排，所以只有前三次跳跃是可能的。

输入格式

The first line of the input will be an integer M (1 ≤ M ≤ 1000). The second line of the input will be an integer N (1 ≤ N ≤ 1000). The remaining input gives the positive integers in the cells of the room with M rows and N columns. It consists of M lines where each line contains N positive integers, each less than or equal to 1 000 000, separated by single spaces. For 1 of the 15 available marks, M = 2 and N = 2. For an additional 2 of the 15 available marks, M = 1. For an additional 4 of the 15 available marks, all of the integers in the cells will be unique. For an additional 4 of the 15 available marks, M ≤ 200 and N ≤ 200. 输入的第一行将是一个整数 $M（1≤M≤1000）$。输入的第二行将是一个整数 $N（1≤N≤1000）$。剩余的输入在 $M$ 行 $N$ 列的房间的单元格中给出正整数。它由 $M$ 行组成，每行包含 $N$ 个正整数，每个正整数小于或等于 $1000 000$，由单个空格分隔。对于 $15$ 个可用标记中的 $1$ 个，$M=2，N=2$。对于 $15$ 个可用标记中的另外 $2$ 个，$M=1$。对于 $15$ 个可用标记中的另外 $4$ 个，单元格中的所有整数都是唯一的。对于 $15$ 个可用标记中的另外 $4$ 个，$M≤200$ 和 $N≤200$。

输出格式

Output yes if it is possible to escape from the room. Otherwise, output no. 如果可以逃离房间，则输出 $yes$。否则，输出 $no$。

3
4
3 10 8 14
1 11 12 12
6 2 3 9

yes

提示

#### 数据范围与提示 Explanation of Output for Sample Input Starting in the cell at (1, 1) which contains a 3, one possibility is to jump to the cell at (1, 3). This cell contains an 8 so from it, you could jump to the cell at (2, 4). This brings you to a cell containing 12 from which you can jump to the exit at (3, 4). Note that another way to escape is to jump from the starting cell to the cell at (3, 1) to the cell at (2, 3) to the exit.

来源

童程童美