New Game 2

Time limit0.5sMemory limit512 MB

Summary
Simulate turns moving K stacked pieces on an N x N colored board, following white, red, and blue square rules, and report the turn when four pieces stack or -1.
Level

Medium7 of 10

Topics
Simulation, Implementation, Linked list, Matrix
Solved
No attempts yet

Problem

Jaehyun decided to make a new game using a chessboard and pieces. The game is played on an N×N chessboard, and the number of pieces is K. The pieces are disk-shaped, and one piece can be placed on top of another. Each square of the chessboard is colored white, red, or blue.

The game starts with K pieces placed on the chessboard. The pieces are numbered from 1 to K, and each has a fixed movement direction. The movement direction is one of four: up, down, left, right.

One turn consists of moving the pieces from piece 1 to piece K in order. When a piece moves, any pieces stacked on top of it move along too. The move depends on the color of the square the piece is trying to move to, as described below. During a turn, the game ends the moment 4 or more pieces are stacked on a single square.

  • The square that piece A is trying to move to:

    • If it is white, piece A moves to that square. If there are already pieces on the target square, piece A is placed on the very top.

      • If there are other pieces on top of piece A, piece A and all pieces above it move together.
      • For example, if pieces are stacked as A, B, C and the target square has D, E, then after piece A moves, the stack is D, E, A, B, C.

    • If it is red, then after moving, the order of piece A and all pieces above it is reversed.

      • If A, B, C move and the target square has no pieces, the stack becomes C, B, A.
      • If A, D, F, G move and the target square has E, C, B, the stack becomes E, C, B, G, F, D, A.

    • If it is blue, piece A reverses its movement direction and moves one square. If the square it tries to move to after reversing is also blue, the piece does not move and stays put.

    • Moving off the chessboard is treated the same as the blue case.

The following is a case with 4 pieces on a 4×4 chessboard.

The first turn proceeds as follows.

The second turn proceeds as follows.

Given the size of the chessboard, the positions of the pieces, and their movement directions, find the number of the turn on which the game ends.

Input

The first line gives the size of the chessboard N and the number of pieces K. The next N lines give the chessboard. Each chessboard entry is an integer, and each integer means the color of a square. 0 is white, 1 is red, 2 is blue.

The next K lines give the pieces, from piece 1 in order. Each piece is described by three integers: the row number, the column number, and the movement direction. Rows and columns are numbered starting from 1, and the movement direction is a natural number no greater than 4, where 1, 2, 3, 4 mean →, ←, ↑, ↓ in order.

No input has two or more pieces on the same square.

Output

Print the number of the turn on which the game ends. If that value is greater than 1,000 or the game never ends, print -1.

Constraints

  • 4 ≤ N ≤ 12
  • 4 ≤ K ≤ 10

Examples5

  1. Example 1

    Input
    4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2
    Expected output
    -1

  2. Example 2

    Input
    4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
1 4 1
    Expected output
    1

  3. Example 3

    Input
    4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
2 4 3
    Expected output
    1

  4. Example 4

    Input
    4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
3 3 3
    Expected output
    2

  5. Example 5

    Input
    6 10
0 1 2 0 1 1
1 2 0 1 1 0
2 1 0 1 1 0
1 0 1 1 0 2
2 0 1 2 0 1
0 2 1 0 2 1
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1
    Expected output
    7