《算法竞赛入门经典》(第2版) 习题3-6 纵横字谜的答案
程序员文章站
2022-06-02 22:15:28
...
题目
习题3-6 纵横字谜的答案(Cross Answers,ACM/ICPC World Final 1994, UVa232)ps: Final???!!!难道是1994年世界总决赛的第一题…哈哈哈哈哈
输入一个r行c列(1<=r,c<=10)的网格,黑格用“ * ” 表示,每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格(即 是黑格或者出了网格边界了),则称这个白格是一个起始格。
首先把起始格编号,接下来找横向单词、竖向单词…不想码字了…上图!!!
英文原题传送门:Virtual Judge网站的UVa原题
这Vjudge真的强,集合了好多好多平台的OJ资源,可以不用傻fufu的等UVa的OJ那2G网速了~~
去看了一下其他人的代码,发现有的好长,100多行,然后,我切身体会到,阅读别人的代码真的好难,每个人有每个人的习惯、思路。
思路
我花了两个半小时,才把这题AC了,一次过的,用的语句就是判断、循环(问就是没其他的语句,就这…目前的菜鸟水平…)加油加油,谁都是这么过来的,你真的真的真的很不错!!!好了好了谢谢大家的鼓励,我会加油的!!!
好了,我总的思路就是 :首先,把题目理解了,这题目好长的说。因为数据量不大,最大就10 X 10的大小,所以用10 X 10的二维数组就能搞定,用一个字符二维数组存放数据,用一个整型二维数组来记录起始格的顺序编号,接着按条件 用循环把结果输出。
总结自己花这么长时间的原因:在按条件 用循环把数据按题目要求输出的时候,折腾了好长的时间,做完其实发现不难(我的代码没算法,很菜,但以AC为目标的话,是不难)。
AC代码
#include <iostream>
#include <string>
using namespace std;
const int maxn = 10; //最大就10行10列
//16:30- 19:40 中间扣掉半小时吃饭
int main() {
int r,c;
char str[maxn][maxn];
int kase = 0;
while (cin >> r) {
if (r == 0) break; //结束方阵的输入
cin >> c;
//输入数据
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> str[i][j];
}
}
kase++;
// cout << "输入完成" << kase << endl;
//开始记录起始格
int sign[maxn][maxn] = {0}; //首先全置为0
int number = 1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (str[i][j] == '*') continue;
if (i - 1 < 0 || str[i-1][j] == '*' || j - 1 < 0 || str[i][j-1] == '*') {
sign[i][j] = number;
number++;
}
}
}
// cout << "起始格:\n";
// for (int i = 0; i < r; i++) {
// for (int j = 0; j < c; j++) {
// cout << sign[i][j] << " ";
// }
// cout << endl;
// }//测试起始格
if (kase > 1) cout << endl;
printf("puzzle #%d:\n", kase);
printf("Across\n");
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (sign[i][j]) {
printf("%3d.", sign[i][j]);
int m = j;
for ( ; m < c && str[i][m] != '*'; m++) {
cout << str[i][m];
}
cout << endl;
j = m;
}
}
}
printf("Down\n");
// for (int j = 0; j < c; j++) {
// for (int i = 0; i < r; i++) {
// if (sign[i][j]) {
// printf("%3d.", sign[i][j]);
// int m = i;
// for ( ; m < r && str[m][j] != '*'; m++) {
// cout << str[m][j];
// }
// cout << endl;
// i = m;
// }
//
// }
// } //这是类似Across的,但是没有按数字大小排序
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (sign[i][j]) {
printf("%3d.", sign[i][j]);
for (int m = i; m < r && str[m][j] != '*'; m++) {
cout << str[m][j];
sign[m][j] = 0; //标志置为0,再遍历到的时候不会重复
}
cout << endl;
}
}
}
}
return 0;
}
上一篇: A Tour of Go练习题汇总