欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法竞赛入门经典》(第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)的网格,黑格用“ * ” 表示,每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格(即 是黑格或者出了网格边界了),则称这个白格是一个起始格。
首先把起始格编号,接下来找横向单词、竖向单词…不想码字了…上图!!!
《算法竞赛入门经典》(第2版) 习题3-6 纵横字谜的答案
英文原题传送门: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;
}