数据结构与算法分析C++习题5.18答案

int main()
{
	int row;
	string str;
	cout << "Enter number of rows in wordArray: ";
	cin >> row;
	while (cin.get() != 'n')
	{
		continue;
	}
	vector> wordArray(row); //输入字谜表
	cout << "Enter elements of wordArray:n";
	for (int i = 0; i < row; i++)
	{
		getline(cin, str);
		for (int j = 0; j < str.length(); j++)
		{
			if (isalpha(str[j]))
			{
				wordArray[i].push_back(str[j]);
			}
		}
	}
	int r = wordArray.size(), c = wordArray[0].size();
	cout << endl;
	cout << "Enter a list of words(q to quit):n"; //输入要从字谜表中查找的单词
	vector words;
	int maxWordSize = 0; //记录单词的最大长度
	cin >> str;
	while (str != "q")
	{
		if (str.size() > maxWordSize)
		{
			maxWordSize = str.size();
		}
		words.push_back(str);
		cin >> str;
	}
	cout << endl;
	cout << "Word position:" << endl;
	unordered_set wordsHash(words.begin(), words.end()); //哈希表存储单词
	unordered_set wordPrefix; //哈希表存储单词的第一个字母
	for (int i = 0; i < words.size(); i++)
	{
		wordPrefix.insert(words[i][0]);
	}
	string temp;
	int k;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (wordPrefix.count(wordArray[i][j])) //当单词的第一个字母包含wordArray[i][j]时查找从（i,j）开始的八个方向是否有匹配的单词。
			{
				temp = "";
				k = 0;
				while (i + k < r && k < maxWordSize)
				{
					temp += wordArray[i + k][j];
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i + k << "," << j << ") " << endl;
					}
					k++;
				}


				temp = "";
				k = 0;
				while (i - k >= 0 && k < maxWordSize)
				{
					temp += wordArray[i - k][j];
					
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i - k << "," << j << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (j + k < c && k < maxWordSize)
				{
					temp += wordArray[i][j + k];
				
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i << "," << j + k << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (j - k >= 0 && k < maxWordSize)
				{
					temp += wordArray[i][j - k];
					
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i << "," << j - k << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (i + k < r && j + k < c && k < maxWordSize)
				{
					temp += wordArray[i + k][j + k];
				
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i + k << "," << j + k << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (i + k < r && j - k >= 0 && k < maxWordSize)
				{
					temp += wordArray[i + k][j - k];
				
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i + k << "," << j - k << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (i - k >= 0 && j - k >= 0 && k < maxWordSize)
				{
					temp += wordArray[i - k][j - k];
					
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i - k << "," << j - k << ") " << endl;
					}
					k++;
				}

				temp = "";
				k = 0;
				while (i - k >= 0 && j + k < c && k < maxWordSize)
				{
					temp += wordArray[i - k][j + k];
				
					if (wordsHash.count(temp))
					{
						cout << temp << ": " << "from " << "(" << i << "," << j << ") " << " to "
							<< "(" << i - k << "," << j + k << ") " << endl;
					}
					k++;
				}
			}
		}
	}
}

示例：