P3848 [TJOI2007] Checkers

This problem may be flawed. The current testdata are randomly generated for $n\leq 20$, and both the testdata and the editorials are for reference only. On an $n \times n$ board filled with 0s and 1s, as shown in Figure (a) (with $n=7$), for convenience, the 0s are labeled with letters, as shown in Figure (b). 

Rules of the game: (1) Starting from some 0-cell, you can jump in one of the four directions (up, down, left, right), consecutively over several (at least one) 1-cells, and land on the next 0-cell. In Figure (b), starting from A, you can jump to B or to E, but not directly to K. After jumping to B, you can continue to F; after jumping to E, you can continue to F or K. Continue until no further jump is possible. (2) Each 0-cell can be visited at most once. The given starting cell cannot be visited again, nor can it be jumped over. The jump distance equals the number of 1-cells jumped over plus 1. For example, from A to B the distance is 3; from B to F the distance is 2. Problem: Given the board and the starting point, what is the maximum total jump distance? In Figure (b), starting from A, there are multiple possible routes. One of them is: A - B - F - L - K - E (possibly not unique) 3 2 3 3 3 Its total distance is 14.

The first line contains three integers: $n$ (1 ≤ $n$ ≤ 100), $x$, $y$ (coordinates of the starting point; in Figure (b), the coordinates of A are 1, 3). Then follow $n$ lines, each containing $n$ numbers (0 or 1), separated by a single space.

Output a single integer: the maximum total jump distance (output 0 if no jump is possible).

$\text{upd 2022.7.27}$：A new hack testdata has been added. Translated by ChatGPT 5