提示: 欢迎访问OurACM平台。
Problem 1892 接水管游戏

Accept: 109    Submit: 504
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

接水管游戏的规则如下:
1、在N*N大小的方格上有两个特别的水管,分别为进水口和出水口;
2、有7种1*1大小的水管需要放在这N*N大小的方格内,使得水流能够从进水口经过这些水管流到出水口;
3、当水流流到了出水口或者水流在流到出水口之前流出了水管,那么游戏就结束了;
4、游戏的分数为水流经过水管的数目(除了进水口和出水口);
5、游戏中有四个方向,分别表示东南西北,可用数字编号说明水管中水流的方向,1表示可以向东流,2表示可以向南流,4表示可以向西流,8表示可以向北流;
6、七种水管的形状如下: :编号为15;:编号为9;:编号为6; :编号为3; :编号为12; :编号为10; :编号为5;
7、进水口的编号需要再加上16,出水口的编号需要再加上32,进水口和出水口中的水流只有一个方向,游戏中有且只有一个进水口和一个出水口;
8、每一时刻,水流都会沿着水管的水流方向流到相邻的方格之中,如果该方格没有水管或者水管接头不对应,那么水流将流出水管。
现在水管已经接好了,请你计算出在当前情况下,能够得到的分数。

Input

输入数据第一行为一整数T,表示有T组输入数据。每组输入数据的第一行为一个整数N(5≤N≤50),表示方格的大小,以下有N行,每行有N个数字Mij(1≤i,j≤N),表示第i行第j列方格中的水管编号,Mij=0表示该方格没有水管。

Output

对于每组数据,输出一行一个整数,表示能够得到的分数。

Sample Input

2 5 3 5 5 6 0 10 3 5 15 6 10 10 0 10 40 10 9 5 12 18 9 5 5 5 12 5 3 5 5 6 0 10 0 0 15 6 10 10 0 0 40 10 9 5 12 18 9 5 5 5 12

Sample Output

18 14

Hint

Source

福州大学第七届程序设计竞赛

Submit  Back  Status  Discuss