Score : $600$ points

问题描述

为 $T$ 个测试用例求解以下问题。

一块棋子位于 $xy$ 平面上的原点 $(0, 0)$。你可以执行任意次数（包括零次）以下操作：

• 选择一个整数 $i$，满足 $1 \leq i \leq 8$ 且 $s_i=$ 1。设 $(x, y)$ 为当前棋子所在的坐标位置。
  • 若 $i=1$，将棋子移动到 $(x+1,y)$。
  • 若 $i=2$，将棋子移动到 $(x+1,y+1)$。
  • 若 $i=3$，将棋子移动到 $(x,y+1)$。
  • 若 $i=4$，将棋子移动到 $(x-1,y+1)$。
  • 若 $i=5$，将棋子移动到 $(x-1,y)$。
  • 若 $i=6$，将棋子移动到 $(x-1,y-1)$。
  • 若 $i=7$，将棋子移动到 $(x,y-1)$。
  • 若 $i=8$，将棋子移动到 $(x+1,y-1)$。

你的目标是将棋子移动到坐标点 $(A, B)$。 找出实现该目标所需的最少操作次数。如果无法实现，则输出 -1。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Solve the following problem for $T$ test cases.

A piece is placed at the origin $(0, 0)$ on an $xy$-plane. You may perform the following operation any number of (possibly zero) times:

• Choose an integer $i$ such that $1 \leq i \leq 8$ and $s_i=$ 1. Let $(x, y)$ be the current coordinates where the piece is placed.
  • If $i=1$, move the piece to $(x+1,y)$.
  • If $i=2$, move the piece to $(x+1,y+1)$.
  • If $i=3$, move the piece to $(x,y+1)$.
  • If $i=4$, move the piece to $(x-1,y+1)$.
  • If $i=5$, move the piece to $(x-1,y)$.
  • If $i=6$, move the piece to $(x-1,y-1)$.
  • If $i=7$, move the piece to $(x,y-1)$.
  • If $i=8$, move the piece to $(x+1,y-1)$.

Your objective is to move the piece to $(A, B)$.
Find the minimum number of operations needed to achieve the objective. If it is impossible, print -1 instead.

Constraints

• $1 \leq T \leq 10^4$
• $-10^9 \leq A,B \leq 10^9$
• $s_i$ is 0 or 1.
• $T$, $A$, and $B$ are integers.

Input

The input is given from Standard Input in the following format:

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

Here, $\mathrm{case}_i$ denotes the $i$-th test case.

Each test case is given in the following format:

$A$ $B$ $s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8$

Output

Print $T$ lines in total.
The $i$-th line should contain the answer to the $i$-th test case.

Sample Input 1

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

Sample Output 1

8
5
5
-1
0
-1
1000000000

update @ 2024/3/10 11:27:15