Vượt Ngục 3

Trong một vụ án mới, FullHouse Dev được yêu cầu phân tích một kế hoạch vượt ngục của tù nhân Alfie. Với khả năng phân tích tuyệt vời, nhóm cần tính toán số đường đi khả thi để giúp các nhà điều tra ngăn chặn kế hoạch này.

Bài toán

Nhà tù có dạng ma trận \(N \times N\). Một số ô trong nhà tù được lắp đặt cảm biến chuyển động. Alfie bắt đầu từ ô \((1,1)\) và cần di chuyển đến ô \((N,N)\) để thoát ra. Từ một ô \((i,j)\), Alfie có thể di chuyển đến các ô \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), \((i,j-1)\) nếu các ô đó nằm trong ma trận và không có cảm biến. Nếu ô đầu tiên \((1,1)\) hoặc ô cuối cùng \((N,N)\) có cảm biến, Alfie không thể thoát ra được.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Với mỗi test case:
  • Dòng đầu chứa số nguyên \(N\) - kích thước ma trận
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số (0 hoặc 1) phân cách bởi dấu cách
  • Số 1 đại diện cho ô có cảm biến chuyển động

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượng đường đi khả thi để thoát khỏi nhà tù

Ví dụ

INPUT

3
4
0 1 1 0 
0 0 1 0 
0 0 0 0 
0 1 1 0 
4
0 0 0 1 
0 0 0 0 
1 1 1 0 
1 0 0 0 
4
0 1 1 0 
0 0 1 1 
0 0 0 0 
0 1 0 0

OUTPUT

2
4
4

Giải thích

• Ở test case đầu tiên, có 2 đường đi khả thi để Alfie thoát khỏi nhà tù
• Ở test case thứ hai, có 4 đường đi khả thi
• Ở test case thứ ba, có 4 đường đi khả thi

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(2 \leq N \leq 10\)