logo AlgoBeat OnlineJudge
登录 注册

#216129. [USTCPC 2026] Blank or Mine

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

克露丝卡尔酱最近又想出了一个新点子。

“如果只能看到一半的信息,还能不能把另一半推出来呢?”她一边在草稿纸上画着小格子,一边自言自语。

社团里的后辈凑过来看了一眼:“诶?这不是扫雷吗?怎么只有上面一排呀?”

“这叫‘半信息扫雷’啦!”克露丝卡尔酱得意地扬了扬笔,“真正的推理,不是靠猜,而是靠必然性哦!”

她把那张只显示第一行信息的棋盘推到你面前,轻轻敲了敲桌面。

“来试试看吧~你能判断出第二行里,哪些格子一定是地雷,哪些一定是空格,哪些又根本无法确定吗?”


你正在玩一个特殊的扫雷游戏。游戏在一个 列()的网格上进行,每个格子要么是地雷,要么是空格。

你已经知道了第一行每个格子是地雷还是空格;如果该格子是空格,你还会看到一个数字,表示它周围八个方向相邻的格子中地雷的总数。

现在,你需要根据这些信息,推断第二行每个格子一定是地雷、一定是空格,还是无法确定。数据保证至少存在一种第二行的布局满足第一行的所有条件。

输入格式

本题有多组测试数据。

第一行一个正整数 ,表示数据组数。

接下来每一行表示一组数据,包含一个长为 的字符串,其中第 个字符表示第一行第 个格子的情况:

  • 如果该格子是地雷,则用字符 * 表示;
  • 如果该格子是空格,则用一个数字字符 08 表示该格子周围八个方向相邻的格子中地雷的总数。

输出格式

对于每组数据,输出一个长度为 的字符串,其中第 个字符表示第二行第 个格子的判断结果:

  • 如果一定是地雷,输出 *
  • 如果一定是空格,输出 .
  • 如果无法确定,输出 ?

样例

样例输入 1

6
*
111
12*21
11112221
*2*3*4*5*
*32*3*23*

样例输出 1

?
.*.
??.??
??.??*??
...???***
*??.*.??*

数据范围与提示

所有数据的 之和 。数据保证至少存在一种第二行的布局满足第一行的所有条件。