题目详情题解（0）讨论（0）提交记录（0）

AT_abc379_g.[ABC379G] Count Grid 3-coloring

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由 1、2、3、? 组成的 HH 行 WW 列的网格 SS。第 ii 行第 jj 列的字符为 Si,jS_{i,j}。

将 SS 中的每个 ? 替换为 1、2、3 中的任意一个，可以得到 3q3^q 种不同的网格（其中 qq 为 ? 的个数）。在这些网格中，有多少种满足以下条件？请输出对 998244353998244353 取模的结果。

  • 任意两个相邻（共享边）的格子中，数字都不相同。

输入格式

输入以如下格式从标准输入读入。

HH WW
S1,1S1,2…S1,WS_{1,1}S_{1,2}\ldots S_{1,W}
S2,1S2,2…S2,WS_{2,1}S_{2,2}\ldots S_{2,W}
⋮\vdots
SH,1SH,2…SH,WS_{H,1}S_{H,2}\ldots S_{H,W}

输出格式

请输出答案。

输入输出样例

  • 输入#1

    2 2
1?
??

    输出#1

    6

  • 输入#2

    2 3
123
3?1

    输出#2

    0

  • 输入#3

    8 8
3?1?????
???1????
??????2?
????????
????????
????13??
??13?1??
????????

    输出#3

    779135038

说明/提示

限制条件

  • 1≤H,W1 \leq H, W
  • H×W≤200H \times W \leq 200
  • H,WH, W 为整数
  • SS 由 1、2、3、? 组成，共 HH 行 WW 列

样例解释 1

将 SS 中的每个 ? 替换为 1、2、3 后，满足条件的网格有如下 66 种：

12
12
12
13
13
13
21
23
31
21
31
32

样例解释 2

将 SS 中的每个 ? 替换为 1、2、3 后，没有任何一种网格满足条件。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页