← 返回题目列表

AtCoder · abc271_h

Ex. 一般一般

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

解决以下问题 T 测试用例。

一块被放置在原点 (0, 0) 上 xy- 平面。 您可以执行以下操作任意次数(可能为零):

  • 选择一个整数 i 这样 1 \leq i \leq 8 和 s_i= 1。 让 (x, y) 是放置棋子的当前坐标。
    • If i=1,将棋子移动到 (x+1,y).
    • If i=2,将棋子移动到 (x+1,y+1).
    • If i=3,将棋子移动到 (x,y+1).
    • If i=4,将棋子移动到 (x-1,y+1).
    • If i=5,将棋子移动到 (x-1,y).
    • If i=6,将棋子移动到 (x-1,y-1).
    • If i=7,将棋子移动到 (x,y-1).
    • If i=8,将棋子移动到 (x+1,y-1).

你的目标是将棋子移动到 (A, B).
找出实现目标所需的最少操作数。 如果不可能,则打印 -1 代替。

约束

  • 1 \leq T \leq 10^4
  • -10^9 \leq A,B \leq 10^9
  • s_i is 0 or 1.
  • T, A,和 B 是整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里, \mathrm{case}_i 表示 i- 第一个测试用例。 总共

每个测试用例均按以下格式给出:

A B s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8

输出

打印 T 行。
的 i- 第行应包含以下问题的答案 i- 第一个测试用例。 总共


示例输入 1

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

示例输出 1

8
5
5
-1
0
-1
1000000000