P1713 Ronald McDonald's Dilemma

Mingming has just answered his dad's question correctly and, of course, wants a reward. His stingy dad spots a newspaper ad: the McDonald's at their doorstep is running a promotion—there is even a free lunch. But there is a catch: you must correctly answer Ronald McDonald's question. The question is as follows: “There are many kids in front of me. I want you to help me find the smartest kid. In my mind, the smartest is the one who first runs into the McDonald's door. I want you to find the maximum possible difference in arrival times between the smartest and the least smart kid. However, the kids can only move according to a special rule. In front of them is an $ n \times n $ grid. The bottom-left cell is the start, and the top-right cell is the door. Each child can move one cell per second in one of the four directions: up, down, left, or right. Each cell can be visited at most once. Some cells in the grid are obstacles and cannot be passed; they must be detoured.” For example, in a $ 4 \times 4 $ grid, cells $ (1, 1), (2, 3), (4, 2) $ are obstacles. The black cells indicate one feasible route. The time is $ 7 $.

The first line contains two integers $ n, m $. Each of the next $ m $ lines describes one obstacle, given by two integers $ x, y $.

Output a single line containing the maximum time difference.

Constraints: $ 2 \le n \le 10 $, $ 0 \le m \le 100 $, $ 1 \le x, y \le n $. Translated by ChatGPT 5