| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
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$)。
每组数据第一行包含一个正整数 $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
1 9 010010000 001000001 000100000 010000000 000001000 000000100 000000010 000010001 000000000
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
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-11-25 02:14:40, Gzip enabled |
Administration |