抓住那只猪02(pig)

题目描述

Y 同学得到了一个大小为 $n \times n$ 的字符方阵，其中每个位置都填有一个小写英文字母。

已知该方阵满足以下条件：

• 方阵中恰好出现了 $n$ 种不同的字母；
• 对于每一种出现过的字母 $c$，恰好有 $1$ 头与之对应的猪；
• 因而一共恰好有 $n$ 头猪。

对于字母 $c$ 对应的那头猪，它只能被放置在字符为 $c$ 的格子上。

现在，Y 同学需要在方阵中为这 $n$ 头猪各选出一个位置，并满足以下要求：

1. 对于任意一头猪，它所选位置上的字符必须等于该猪对应的字母；
2. 每一种字母恰好被选中一次；
3. 任意两头猪不能位于同一行；
4. 任意两头猪不能位于同一列；
5. 任意两头猪不能在八个方向上相邻。更形式化地说，若两头猪分别位于 $(x_1,y_1)$ 与 $(x_2,y_2)$，则不能同时满足$$\lvert x_1-x_2\rvert \le 1,\ \lvert y_1-y_2\rvert \le 1 $$且 $(x_1,y_1)\ne(x_2,y_2)$。

请你输出所有满足条件的合法方案，并按字典序从小到大输出。

对于任意一个合法方案，由于共有 $n$ 头猪且任意两头猪不能位于同一行，因此每一行恰好会选出一个位置。记第 $i$ 行被选中的列号为 $p_i$，则该方案可唯一表示为长度为 $n$ 的序列

规定方案 $(p_1,p_2,\dots,p_n)$ 的字典序小于方案 $(q_1,q_2,\dots,q_n)$，当且仅当存在最小的正整数 $t$，满足：

• 对于所有 $1 \le i < t$，都有 $p_i=q_i$；
• 且 $p_t<q_t$。

你需要按照上述字典序输出全部合法方案。

坐标从 $1$ 开始计数，左上角位置记为 $(1,1)$。

输入格式

第一行输入一个整数 $n$，表示方阵的大小，同时也表示猪的数量。

接下来输入 $n$ 行，每行一个长度为 $n$ 的字符串，表示该字符方阵。

输出格式

第一行输出一个整数 $k$，表示合法方案的总数。

接下来输出 $k$ 行，第 $i$ 行输出第 $i$ 个合法方案。

对于每个方案，输出 $n$ 个整数 $p_1,p_2,\dots,p_n$，其中 $p_j$ 表示该方案中第 $j$ 行被选中位置的列号。相邻两个整数之间用一个空格分隔。

所有方案必须按字典序从小到大输出。

样例

样例输入 #1

4
dadb
ddbb
cddd
bddd

样例输出 #1

1
2 4 1 3

样例解释

方阵为：

按题意，每种字母对应一头猪，且任意两头猪不能同行、同列，也不能在八个方向相邻。

样例中的唯一合法方案为：

• 第 $1$ 行选第 $2$ 列；
• 第 $2$ 行选第 $4$ 列；
• 第 $3$ 行选第 $1$ 列；
• 第 $4$ 行选第 $3$ 列。

对应序列为：

检查可知：

• 这四个位置上的字母两两对应不同的猪；
• 没有两头猪位于同一行或同一列；
• 也没有两头猪在八个方向相邻。

数据范围与约定

对于 $100$ 的数据，保证 $1 \le n \le 10$，方阵中的字符均为小写英文字母，方阵中恰好出现了 $n$ 种不同的字符，合法方案总数不超过 $5 \times 10^5$。

• 特殊性质 A：每种字母在方阵中恰好出现 $1$ 次。
• 特殊性质 B：对于任意一种字母，其在方阵中的出现次数不超过 $2$。
• 特殊性质 C：合法方案总数不超过 $10$。