Skip to content

11229: 【原1229】mine

题目

题目描述

author: Hao Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1229

Description

扫雷是一个很经典的小游戏,而一行数字一行雷的题目就更经典了。当然,这道题不能这么简单就算了。

问题是这样,有一个两行n列的格子,第一行里不会有雷,第二行里不会有数字。给定第一行的某些数字,数字代表该格子正下方与左右两个斜下方共三个格子里雷数目的总和。问下一行最多有多少个雷,并给出一个让雷尽可能靠后的方案(最后一个雷尽可能靠后,如果相同,倒数第二个雷尽可能靠后,以此类推)。保证一定存在一种合法的地雷安放方案。

Input Format

第一行一个整数n,表示格子的列数

第二行为一个长度为n的字符串,由‘0’、‘1’、‘2’、‘3’以及‘*’组成。表示第一行的数字,‘*’表示该格数字未定,保证不含其他字符(行末回车符除外)

Output Format

第一行为一个整数,表示最多的地雷数目

第二行为一个长度为n的字符串,由‘0’和‘1’组成,‘0’代表安全,‘1’代表有地雷。表示所要求的安放方案

Sample Input

2
1*

Sample Output

1
01

数据规模

10%数据 :1<=n<=10 40%数据 :1<=n<=100000,输入中不出现‘*’号 100%数据:1<=n<=100000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!