U119904 迷宫（加强版）

这里是求最短路径、多组数据的加强版。要查看带有$\text{Special Judge}$的弱化版的，请移步[这里](/problem/U119869)。

已知$T$个$N\times N$的$0-1$迷宫，允许往上、下、左、右四个方向行走。请你找出任意一条从左上角到右下角的路径，无法到达则输出$-1$。本题没有$\text{Special Judge}$，所以为了保证路径唯一，搜索需要严格按照**左、右、上、下**的顺序进行拓展。

输入$T$个迷宫。 对于每一个迷宫，输入第一行有一个自然数$N$，表示迷宫的大小。 接下来的$N$行，每行有$N$个$0$或$1$（$0$表示可以通过，$1$表示不能通过），用以描述迷宫地图。入口在左上角$(1,1)$处，出口在右下角$(N,N)$处。

对于每一个迷宫，如果能够到达终点，就输出最少步数和路径（换行符隔开），否则输出$-1$。 每两个迷宫之间的输出用换行符隔开。

对于$\text{Subtask 1 (10 pts)}$，满足$T\le 5$，$∀N\le 5$，时间限制为$\text{1s}$。 对于$\text{Subtask 2 (30 pts)}$，满足$T\le 10$，$∀N\le 10$，时间限制为$\text{1s}$。 对于$\text{Subtask 3 (60 pts)}$，满足$T\le 20$，$∀N\le 20$，时间放宽到$\text{2s}$，保证朴素的$\text{DFS}$不超时。 对于$100\%$的数据，$1\le T\le 20$，$2\le ∀N\le 20$，每一个迷宫的$(1,1),(N,N)$位置的数字都是$0$。 附件中提供了两组$T=20$的大样例，仅供参考。 |测试点编号|隶属子任务编号|$T$|$∀N$|特殊性质|时间限制| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$1$|$1$|$=1$|$\le 5$|输出不包含$-1$|$\text{1s}$| |$2$|$1$|$\le 5$|$\le 5$|无|$\text{1s}$| |$3,4$|$2$|$\le 10$|$\le 10$|无|$\text{1s}$| |$5$|$2$|$\le 10$|$\le 10$|输出不包含$-1$|$\text{1s}$| |$6$|$2$|$\le 10$|$\le 10$|无|$\text{1s}$|$3$| |$7,8,9,10$|$3$|$\le 20$|$\le 20$|无|$\text{2s}$|$10$| 注：$∀$读作“任意的”，这里指每一组数据中的$N$都满足对应的条件。