Logo Universal Online Judge

UOJ

时间限制:N/A 空间限制:N/A

#2978. 字符串(string)

统计

题目描述

你现在有 $n$个长度为 $m$ 的字符串 $S_1,\dots,S_n$ ,满足字符集为 ${1,2,\dots,n}$。你还有一个长度为 ¥吗¥ 的模式字符串 $T$,模式串的每个位置上除了 ${1,2,\dots,n}$ 之外还可以有一个通配符 $0$。

现在,$n$ 个字符串排成了一个环,对于 $S_i$,它右边的字符串为 $S_{(i \ \bmod \ 1)+1}$;而对于 $S_{(i \ \bmod \ 1)+1}$,它左边的字符串 $S_i$。

现在,我们在串 $S_a$ 处,然后我们希望能达到串 $S_b$。初始的时候,$T$ 的每一位都是 $0$。每一回合,加入当前处于 $S_x$,你可以进行如下的操作之一:

  • (操作一)从 $S_x$ 的右边的串开始,不断向右移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。
  • (操作二)从 $S_x$ 的左边的串开始,不断向左移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。
  • (操作三)将 $T$ 任意一个字符为 $0$ 的位置更改为 ${1,2,\dots,n}$ 中的任意一个数。更改完毕后,如果 $T$ 仍然能匹配 $S_x$,那么次回合中不移动;否则会不断向右移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。注意,如果不存在 $y$ 使得 $S_y$ 与 $T$ 匹配,那么这回合的操作是非法的,会直接死机。
  • (操作四)将 $T$ 任意一个字符非 $0$ 的位置更改为 $0$,不移动。

请你对于所有的 $a,b$,都求出:如果初始在 $S_a$ 处,在满足所有回合操作都合法的情况下,最少需要多少个回合可以到达 $S_b$。

输入格式

第一行两个正整数 $n,m$

后面 $n$ 行,每行 $m$ 个正整数,描述一个字符串。

输出格式

$n$ 行,每行 $n$ 个整数。第 $i$ 行的第 $j$ 个正整数表示 $a=i,b=j$ 时的答案。

样例输入 1

4 1
4
2
3
2

样例输出 1

0 1 1 1 
1 0 1 2 
1 1 0 1 
1 2 1 0

样例解释 1

$a=1,b=2$ 时,进行一次操作一即可;$a=1,b=3$ 时,进行一次操作三,操作三中将 $T$ 的唯一一位从 $0$ 更改成 $3$ 后会直接移动到 $S_3$。$a=2,b=4$ 时,若第一步就进行操作三把 $T$ 更改为 $2$ 的话就还会待在原地;而问你应该直接做两次操作一来得到最优解。

样例输入 2

6 3
1 3 2
2 1 1
2 1 2
1 3 3
1 3 2
2 3 2

样例输出 2

0 1 2 1 2 1 
1 0 1 1 2 2 
2 1 0 1 2 2 
2 1 1 0 1 1 
2 1 2 1 0 1 
1 1 2 1 1 0

大样例

link

数据范围

对于所有的数据,满足 $2\leq n \leq 500$,$1 \leq m \leq 5$

$\text{Subtask 1(10 pts)}$ $m \leq 1$,$n \leq 50$。

$\text{Subtask 2(10 pts)}$ $m \leq 2$,$n \leq 150$。

$\text{Subtask 3(10 pts)}$ $m \leq 3$,$n \leq 250$。

$\text{Subtask 4(10 pts)}$ $m \leq 4$,$n \leq 350$。

$\text{Subtask 5(10 pts)}$ $m \leq 5$,$n \leq 300$。

$\text{Subtask 6(10 pts)}$ $m \leq 5$,$n \leq 500$。