P1933 [NOI2010] Travel Route

In 2010, the World Expo was held in Shanghai, China, attracting tens of millions of visitors from home and abroad. During the summer vacation, Xiao Z also came to the Shanghai Expo Park. She had heard that the Expo Park would be very crowded, and some pavilions might require queuing for several hours. She was fully prepared for that. To make her trip smoother and more enjoyable, Xiao Z decided to plan a detailed travel route before visiting. Xiao Z collected a map of the Expo Park and found that, overall, the park is a very long and narrow area, and each pavilion occupies one square of almost the same size. Therefore, the entire park can be seen as an $n \times m$ matrix ($n \leq 3$), where each cell represents a themed pavilion. Since different pavilions have different levels of popularity, the queueing times also differ. Based on statistics, Xiao Z marked each pavilion $(x, y)$ with $T_{x,y} = 0$ or $1$. If $T_{x,y} = 1$, it means the pavilion is very popular and requires a long queue; if $T_{x,y} = 0$, it means the pavilion is relatively ordinary and can be entered with almost no queue. Xiao Z wants to plan a reasonable route so that she alternates between popular and ordinary pavilions. This way, she will neither spend too long queueing at popular pavilions nor find the trip too dull by only visiting ordinary ones. Also, Xiao Z values efficiency: she hopes to visit all pavilions without taking unnecessary detours. Therefore, she wants the travel route to satisfy the following constraints: 1. After visiting the pavilion at $(x, y)$, the next pavilion to visit is an adjacent and unvisited pavilion $(x^\prime, y^\prime)$, i.e., $|x - x^\prime| + |y - y^\prime| = 1$. 2. The starting point of the route lies on the boundary of the matrix, i.e., $x = 1$ or $x = n$ or $y = 1$ or $y = m$. She prepares a 0/1 sequence $L$ of length $n \times m$. She wants the $i$-th visited pavilion $(x, y)$ to satisfy $T_{x,y} = L_i$. Xiao Z wants to know how many different travel routes satisfy her requirements. Since the final answer can be large, she only wants the total number of feasible routes modulo $11\,192\,869$.

- The first line contains two positive integers $n, m$. - Lines $2$ to $n+1$: each line contains $m$ 0/1 integers. In line $i+1$, the $j$-th number represents $T_{i,j}$. - Line $n+2$ contains $n \times m$ 0/1 integers, where the $i$-th number represents $L_i$.

Output a single integer: the total number of feasible travel routes modulo $11\,192\,869$.

Sample explanation: The four feasible travel routes are: $$ \begin{aligned} (1,1) \to (1,2) \to (2,2) \to (2,1)\\ (1,1) \to (2,1) \to (2,2) \to (1,2)\\ (2,2) \to (1,2) \to (1,1) \to (2,1)\\ (2,2) \to (2,1) \to (1,1) \to (1,2) \end{aligned} $$ Constraints: - For $10\%$ of the testdata: $n = 1$. - For $30\%$ of the testdata: $n = 2$. - For $60\%$ of the testdata: $n = 3$, and for $20\%$ of the testdata, all $T_{i,j}$ are $0$. - For $100\%$ of the testdata: $m \leq 50$, $L_i, T_{i,j} = 0$ or $1$. Translated by ChatGPT 5