#P2548. [AHOI2004] 智能探险车

[AHOI2004] 智能探险车

题目描述

Sanuel 星球上的科学探险活动是由名为 Smart 的智能探险车完成的。因为 Sanuel 星球远离地球,信号往返传送一次要耗费数小时,而且存在很高的误码率。因此科学家们无法在地球上对 Smart 探险车进行实时控制,绝大部分探险活动都是由该探险车通过分析环境要素、自主决策、自主完成的。

科学家们的探险车设计方案相对简单:

首先,总结出影响探险车决策的各种决策因素,譬如:天气(weather)、地形(landform)、探险车供电情况(energy)和已采集矿石数目(mine)等。

随后,将每一种决策因素分成两种主要情况。譬如,将天气分成晴朗(sunny)和大风(windy);将探险车供电情况分成饱满(full)和匮乏(lack),等等。

再后,科学家们针对各种决策因素,分别列出每一种行为的决策条件。譬如,若影响采集矿石的决策因素有 N=4N=4 种,而采集矿石的决策条件如下:

决策条件 Weather Landform Energy Mine
1 sunny Plain full Few
2 mountain Many
3

探险车的行为及其决策条件都很多,为了提高探险车的决策速度,最后需要探险车上的智能归纳模块将每一种行为的各种决策条件总结成一条“决策模板”。

如上述采集矿石的各条决策条件可以总结为:

决策模板 sunny * full *

其中,“*”表示该因素不影响探险车的行为决策。

显然,决策模板要能够涵盖科学家们列出的该行为的所有决策条件。同时,决策模板中也含有一些科学家们未列出的决策条件,因而探险车能够在科学家们没有给出的决策条件下也能够自动进行某种行为,因而具有一定的“智能性”。如,上述决策模板会导致探险车在以下决策条件下也会进行矿石的采集。

Weather Landform Energy Mine
新决策条件 sunny Plain full Many

但是,任何事物都存在着两个方面。如果给出的决策模板过于笼统就失去了决策意义,相当于决策不精确。如,以下决策模板虽然涵盖了科学家们列出的各种采集矿石决策条件,但是因为决策过于笼统而意义不大。

过于笼统的决策模板 * full *

因此,要求探险车的决策模板所使用的”*“尽可能少。

小可可负责领导开发探险车的智能归纳模块。请你编写程序帮助小可可完成任务。

输入格式

第一行有两个用一个空格隔开的正整数 NNMM ,分别表示决策因素(N100N \leq 100)和某种行为的决策条件数目(M1000M \leq 1000)。

接下来的 MM 行每行是由 NN 个单词构成的字符串,每个单词依次对应一种决策因素的情况,每行就表示一种决策条件。每行内的单词之间用一个空格隔开。

注意:每行的行首与行末都不存在多余的空白字符,单词仅仅由小写英文字母构成,长度不超过 10。

输出格式

只有一行,表示决策模板,由 NN 个单词或“*”构成,彼此间用一个空格隔开。要求行首与行末都不存在多余的空白字符。

4 3
sunny plain full many
sunny mountain full many
sunny mountain full few
sunny * full *