UC知道请C/C++高手帮我看看这个问题吧。
来源：百度知道 编辑：UC知道 时间：2024/05/12 06:48:23
题目：
神秘的首都名。如下图中的字母块阵中藏着九个首都名DUBIN、TOKYO、LONDON、ROME、BONN、PARIS、ZURICH、OSLO、LIMA，试设计一程序指出首都名的起始字母在方阵中的行列号及字母的走向。（要用图论的知识到来编程）
字母方块阵
O K D U B L I N
A L P G O C E V
R A S M N S M B
O S L O N D O N
Y I B L H L R C
K R Z U R I C H
O A I B X M U Z
T P Q G L A M V
输出结果如下
name: row: col: direction:
DUBIN 1 3 right
TOKYO 8 1 up
LONDON 4 3 right
ROME 5 7 up
BONN 1 5 down
PARIS 8 2 up
ZURICH 6 3 right
OSLO 4 1 right
LIMA 5 6 down
我不需要你们提供我详细程序，我只需要你们提供我一下解题思路，谢谢！
神秘的首都名。如下图中的字母块阵中藏着九个首都名DUBIN、TOKYO、LONDON、ROME、BONN、PARIS、ZURICH、OSLO、LIMA，试设计一程序指出首都名的起始字母在方阵中的行列号及字母的走向。（要用图论的知识到来编程）
字母方块阵
O K D U B L I N
A L P G O C E V
R A S M N S M B
O S L O N D O N
Y I B L H L R C
K R Z U R I C H
O A I B X M U Z
T P Q G L A M V
输出结果如下
name: row: col: direction:
DUBIN 1 3 right
TOKYO 8 1 up
LONDON 4 3 right
ROME 5 7 up
BONN 1 5 down
PARIS 8 2 up
ZURICH 6 3 right
OSLO 4 1 right
LIMA 5 6 down
我不需要你们提供我详细程序，我只需要你们提供我一下解题思路，谢谢！
图论知识不大会,但是我要是来编这个程序的话,我会考虑两个循环.
先将九个首都列为一个枚举类型的值.
将字母方块列为一个二维数组的值(如a[8,8])
从你的题看,只有上下左右四种走向.而九个首都中每一个都最少有四个字母.
因此我会第一个循环,检查每一列的排行可能的结果,如O K D U B L I N这一列,从O开始,取四个字母,五个字母,六个,这样,下一次再从K开始,一直到从U开始就结束.当然我们还应该定义一个字符串反向排序的函数,这样把每一个组合的字符串同枚举中的结果对比,如果组合对比成功,就是right,如果反向对比成功,就是left.
每一行循环完毕后,再循环列,同样的....
。。。。。。。。。。。。。。。。。。200分估计都不会有人愿意帮
我觉得你用图论来吓唬大家了!
其实你只要搜索出每个每个字母的位置,想办法把他们之间的连线画出来,然后自己看一下,应该是比较简单的!
大家有谁愿意参加我的C语言编程群啊22453400
说明,群是刚开始建立的,希望大家能够积极提出问题和解决问题啊!
这样如何：枚举第一个字母，广搜（根据对应单词长度控制深度）
复杂度:O(n^2 * 4^maxlen)，其中maxlen为单词最长长度
先找到第一个字母，以这个字母为中心去它的山下左右找第二个字母，以此类推