PIPIOJ

Problem1526--最短路径问题

1526: 最短路径问题

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 142 Solved: 57
[Submit] [Status] [Web Board] [Creator:]

Description

有一个 $2n$ 的迷宫， $0$ 表示可以走， $1$ 表示是障碍。
如果格子 $x_1,y_1$ 和 $x_2,y_2$ 都是可以走且同时满足 $|x_1-x_2|\le 1$ 和 $|y_1-y_2|\le1$ ，则 $PIPI$ 可以从格子 $x_1,y_1$ 走到 $x_2,y_2$ 。
请输出 $PIPI$ 从 $1,1$ 走到 $2,n$ 的最短路径距离是多少，如果无法走到，输出 $-1$ 。

Input

第一行一个整数 $t(1\le t\le 100)$ 表示测试用例的组数
对于每组测试用例：
第一行一个整数 $n(2\le n\le 1000)$
第二行一个长度为 $n$ 的字符，表示迷宫第一行的状态，字符串仅可能包含 $0$ 、 $1$ 两种字符
第二行一个长度为 $n$ 的字符，表示迷宫第二行的状态，字符串仅可能包含 $0$ 、 $1$ 两种字符
保证格子 $1,1$ 和格子 $2,n$ 为 $0$ 。

Output

输出 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试用例的答案

Sample Input

Sample Output

2
3
-1

Source/Category

简单

[Submit] [Status]