#P4599. [Sdoi2016]墙上的句子

    ID: 1839 传统题 1000ms 512MiB 尝试: 68 已通过: 24 难度: 8 上传者: 标签>难度分类提高+/省选-图论最小割建模Dinic最大流最小割定理当前弧优化CF2400

[Sdoi2016]墙上的句子

[SDOI2016] 墙上的句子

题目描述

一面墙被划分成 nn 行 mm 列的格子。每个格子是空白,或写有一个大写英文字母。每一行或列中,相邻空白或边界之间的极长连续字母段构成一个单词。行可从左往右或从右往左读,列可从上往下或从下往上读。每行或列的所有单词采用该行或列的同一阅读方向。

保证每一行或列独立地满足以下一种情况:其中每个单词的字典序都不大于自身反转后的字典序,或都不小于自身反转后的字典序。各行列可以满足不同的情况。

有些行列的阅读方向已知,其余可以任选。确定所有阅读方向后,将全部读出的不同单词收录为字典。求字典中反转后仍在字典中的单词种数的最小值。若一对互为反转的不同单词均被收录,两种都计入。任意被收录的回文单词计一次。

输入格式

第一行一个整数 TT,表示测试组数。每组测试依次给出:

  1. 两个整数 n,mn,m,表示行数和列数。
  2. nn 个整数,依次给出各行的方向。11 表示从左往右,−1-1 表示从右往左,00 表示方向未知。
  3. mm 个整数,依次给出各列的方向。11 表示从上往下,−1-1 表示从下往上,00 表示方向未知。
  4. nn 行,每行一个长度为 mm 的字符串,只包含大写英文字母和下划线。下划线表示空白格。

输出格式

输出 TT 行,每组输出可以得到的最小单词种数。

1
2 10
0 0
0 0 0 0 0 0 0 0 0 0 
ADA_JARVIS
ADA_SIVRAJ
3

数据范围

1≤n,m≤721\le n,m\le72,1≤T≤641\le T\le64。