P8224 [WFOI - 02] I wanna cross the grid (Crossing the Grid).

> People who believe in miracles are greater than miracles themselves. Suddenly, the save point dropped into a huge grid. Only after walking through all required areas will the next save point appear...

You are given a grid with $n$ rows and $m$ columns. Rows and columns are numbered starting from $1$. Define an ordered pair $(x,y)$ to represent the cell at row $x$, column $y$. In each row, the cells from column $L$ to column $R$ are required areas. Formally, let $D$ be the set of required areas, then $D=\{(x,y)|1\leq x\leq n,L\leq y\leq R,x,y\in N_+\}$. Each time, kid can move one step in one of the four directions: up, down, left, or right, and cannot go out of bounds. Formally, if kid is currently at $(x,y)$, then kid can move to $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$. Initially, kid is at $(S_x,S_y)$ (it is guaranteed that $S_y=L$). He needs to walk through all required areas, and any cell can be visited at most once. Formally, kid’s path is a sequence of ordered pairs $P=(x_1,y_1),(x_2,y_2)...(x_k,y_k)$, which must satisfy: for all $(x_0,y_0)\in D$, there exists $i\in[1,k]$ such that $(x_0,y_0)=(x_i,y_i)$, and for all $i\not= j$, $(x_i,y_i)\not= (x_j,y_j)$. Meanwhile, kid must record a clearing sequence $p$. After kid enters the required area of a certain row for the first time, he must append that row number to the end of the current sequence, and immediately traverse all required areas of that row. Also, $p$ must contain a subsequence $q$ of length $L_q$ to be a valid clearing sequence and truly clear the level. Formally, $p$ is valid if and only if there exists a sequence $c$ of length $L_q$ such that $p_{c_i}=q_i$, and $c$ is strictly increasing. Also, to reduce the operation difficulty for lindongli2004, lindongli2004 hopes that kid uses as few steps as possible. Given $n,m,L,R,S_x,S_y,q$, please plan a clearing route for kid, or tell him that no such route exists. The remaining operations will be left to lindongli2004!

The first line contains $8$ positive integers $n,m,L,R,S_x,S_y,L_q,s$, representing the number of rows and columns of the grid, the left and right boundaries of the required area, the starting $x$ and $y$ coordinates, the length of sequence $q$, and the scoring parameter. The second line contains $L_q$ distinct positive integers, representing the sequence $q$.

The first line outputs a string `YES` or `NO` indicating whether a path exists (without quotes). If a path exists, the second line outputs a positive integer $cnt$ indicating the path length. Then output $cnt$ lines, each with two positive integers $x,y$ representing the coordinates on the path.

#### Constraints $1\leq L\leq R\leq m$, $1\leq S_x\leq n$, and for the rest see the provided files. #### Scoring Rules The last number in the first line of the provided files is $s$. Let your number of steps be $cnt$. Then: - If $cnt\leq s$, you will get $10$ points. - If $cnt> s$ and you can clear the level, you will get $9- \frac{cnt-s}{\lfloor\frac{n}{2}\rfloor}$ points. - If you cannot clear the level, you will get $0$ points. #### Checker [Self-service](/paste/c4omcrf2). How to use: In the same directory, put the provided testdata into `data.in`, put your output into `data.out`, compile and run. Notes: - This checker assumes there exists a solution by default, and checks whether that solution is valid. - The maximum capacity of solutions for this checker is $2.5 \times 10^{8}$. That is, your solution cannot contain more than $2.5 \times 10^{8}$ numbers. Translated by ChatGPT 5