Best Coder ^beta
VIP | STD Contests
DIY | Web-DIY ^beta

矩阵的周期

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 42 Accepted Submission(s): 17

Problem Description

给定一个

$n\times n$ 的01矩阵

$\textbf{M}$ ，令

$f ( i , j , k ) = [(\textbf{M}^k)_{i,j}\neq 0]$ ，请对于每对

$(i,j)$ (

$1\leq i,j\leq n$ )，找出最小的正整数

$t$ ，满足当

$k$ 充分大时必有

$f ( i , j , k ) = f ( i , j , k + t )$ 。

Input

第一行包含一个正整数

$T$ (

$1\leq T\leq 20$ )，表示测试数据的组数。

每组数据第一行包含一个正整数

$n$ (

$1\leq n\leq 60$ )，表示矩阵的大小。

接下来

$n$ 行，每行一个长度为

$n$ 的01串，第

$i$ 行第

$j$ 列表示

$\textbf{M}_{i,j}$ (

$1\leq i,j\leq n$ )。

Output

对于每组数据输出

$n$ 行，第

$i$ (

$1\leq i\leq n$ ) 行输出

$n$ 个整数，其中第

$j$ (

$1\leq j\leq n$ ) 个整数表示最小的正整数

$t$ ，满足当

$k$ 充分大时必有

$f( i , j , k ) = f ( i , j , k + t )$ ；若找不到这样的

$t$ ，输出 ''

$\texttt{-1}$ ''。

Sample Input

Sample Output

1 3 3 3 4 4 4 4 12
1 3 3 3 1 1 1 1 3
1 3 3 3 1 1 1 1 3
1 3 3 3 1 1 1 1 3
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 1 1 1 1 1 1 1

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2025 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2025-04-01 06:38:07, Gzip enabled

Administration