National Olympiad in Informatics, China, 2010

Day 2, Problem 2 - Route Planning

The 2010 World Expo will be hosted in Shanghai, China, attracting millions of tourists from within and outside of China. Little Z has also arrived at Expo 2010 in his summer vacation. She has known about the infamous crowdedness of the world's fair. She is already very prepared to wait many hours in line at certain pavilions, but to make her trip at the Expo even smoother, little Z decided to plan a detailed route.

Little Z has gotten her hands on a map of the Expo, and she noticed that the site of the whole event is very narrow and long. Within it, each pavilion occupies a square region which are all roughly the same size. Thus, we can view the entire Expo as an n×m grid (n ≤ 3), where each grid cell represents a theme pavilion.

Since the attention received by different pavilions differ, the length of time spent waiting in their lines will also vary. Through statistical data, Little Z has labeled each pavilion (x, y) with a number T_{x, y} equaling either 0 or 1. If T_{x, y} = 1, then this pavilion is really popular and will demand a very long wait. If T_{x, y} = 0, then this pavilion is relatively average, and will require virtually no waiting at all to enter. Little Z wishes to design a reasonable route which alternates between popular and average pavilions, such that she won't have to wait in line for too long because she's always visiting popular pavilions, but also won't have to feel bored because she's always visiting average pavilions. At the same time, little Z really values efficiency; she wishes to avoid unnecessary walking when visiting all the pavilions. Thus she wishes for her route to satisfy the follow conditions:

1. After visiting the pavilion at location (x, y), the next pavilion she visits must be a neighboring pavilion (x', y') that has not already been visited, where | x − x' | + | y − y' | = 1.
2. The route's starting position must be on the border of the entire grid, where either x = 1, or x = n, or y = 1, or y = m. She has formulated a 01-sequence L of length n×m, wishing for her i-th visited pavilion (x, y) to satisfy Tx, y = L_i.

Little Z wishes to know how many possible routes can satisfy these requirements. Since the final answer can be really large, little Z would only like to know the number of possible routes modulo 11192869.

Input Format

The first line contains two positive integers n and m.
For lines 2 to n + 1, each line contains a 01 sequence of length m, where the j-th digit on line i + 1 represents T_{i, j}.
Line n + 2 contains a 01-sequence of length n×m, where the i-th digit represents the value of L_i.

Output Format

The output should contain a single integer, representing the number of valid routes that satisfy the requirements, modulo 11192869.

Sample Input

2 2
10
01
1010

Sample Output

4

Explanation

The four valid routes are:

• (1, 1) → (1, 2) → (2, 2) → (2, 1)
• (1, 1) → (2, 1) → (2, 2) → (1, 2)
• (2, 2) → (1, 2) → (1, 1) → (2, 1)
• (2, 2) → (2, 1) → (1, 1) → (1, 2)

Constraints

For 10% of the test cases: n = 1.
For 30% of the test cases: n = 2.
For 60% of the test cases: n = 3, and 20% of the test cases have T_{i, j} all equal 0.
For 100% of the test cases: m ≤ 50, and L_i, T_{i, j} = 0 or 1.

All Submissions
Best Solutions

Point Value: 35 (partial)
Time Limit: 5.00s
Memory Limit: 512M
Added: Aug 08, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)