题一：纵横字谜(UVa232)
题意：输入一个r行c列的网格，黑格用*号表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。首先把所有起始格从左到右，从上到下顺序编号1，2，3，。。。。要求找出所有横向单词。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右边。最后找出所有的竖向单词。
输入案例：
输出案例：
思路：
（1）用二维数组存储输入的网格
（2）由于题目需要起始格，我们得先找出起始格的位置才能判断单词输出，这一部分可以在输入的部分同步完成。
（3）先输出横向的单词再输出纵向的单词
遇见困难：
（1）莫名其妙输出单词的时候总是会越界（烫烫烫烫烫）
解决办法：手动加入判定避免输出越界。
（2）在输出纵向的单词的时候，如果是一列一列判断：
如上图，那么输出应该是先A、US、I，但显然不是，题目要求要以起始格顺序输出。
解决办法：先把那些单词找出来，然后再将这些单词存储到另外一个二维数组里面，按照起始格顺序输出。
代码如下：
#include<iostream>
#include<string>
using namespace std;
int main(void)
{
int i, j;
int r, c;
int num = 0;
char str[15][15] = { 0 };
char word[10]={0};
char strcopy[100][100] = { 0 };
int position[15][15];
int position_number = 1;
cin >> r;
cin >> c;
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
cin >> str[j][i];
if (str[j][i] != '*' && (j-1<0||i-1<0)&& str[j][i] != 0) position[j][i] = position_number++;
else if(str[j][i] !='*'&&(str[j-1][i]=='*'|| str[j][i-1]=='*') && str[j][i] != 0) position[j][i] = position_number++;
}
}
position_number = 1;
cout << "Across"<< endl;
//先计算横向
for (i = 0; i <=r; i++)
{
for (j = 0; j <=c; j++)
{
if (str[j][i] == '*'||j==r)//是黑格或者到达了边界
{
word[num] = 0;
if(strlen(word)!=0) cout << position_number << "."<< word << endl;
memset(word, '\0', sizeof(word));
if (j + 1 < c) position_number = position[j + 1][i];
else if (j + 1 == c && i + 1 != r)position_number = position[0][i+1];
num = 0;
}
else if(j<c) word[num++] = str[j][i];
}
}
position_number = 1;
cout << "Down" << endl;
//再计算纵向
for (i = 0; i <= r; i++)
{
for (j = 0; j <= c; j++)
{
if (str[i][j] == '*' || j == r)
{
word[num] = 0;
if (strlen(word) != 0)strcpy(strcopy[position_number],word);
memset(word, '\0', sizeof(word));
if(j + 1 < c ) position_number = position[i][j+1];
else if(j + 1==c&&i!=r)position_number = position[i+1][0];
num = 0;
}
else if (j < c) word[num++] = str[i][j];
}
}
for(i=0;i<50;i++)
if(strcopy[i][0]!=0)
cout << i << "." << strcopy[i] << endl;
}
碎碎念：感觉是很简单的题目但总是会莫名其妙出现很多细节错误。做出来后感觉是不是做的太长了，但查一下好像很多人都很长，心态平衡了不少。运行截图如下：
题二：DNA序列
题目描述：
输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1,4字符不同）。
输入整数m和n(4<=m<=50,4<=n<=1000),以及m个长度为n的DNA序列（只是包含字母A,C,G,T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
怎么说呢，我一开始被唬得一愣一愣的，觉得是个很牛逼的题目，看懂题目后发现是一道水题。
所谓的Hamming距离就是指字符串相似度，ACGT和GCGA有两个字母不同，所以距离为2，那么所谓的最优解，即DNA每一个组成字母都是给予的DNA系列中出现次数最多的。比如说上面例子的第一纵为TTATT，T出现最多，所以最优解第一个字母就是T，以此类推即可得出最优解。
代码如下：
#include<iostream>
#include<string>
using namespace std;
int max_func(int A, int C, int G, int T)
{
int max_num;
max_num = A;
if (C > max_num) max_num = C;
if (G > max_num) max_num = G;
if (T > max_num) max_num = T;
return max_num;
}
int main(void)
{
int i, j;
int m, n;
int A_num,C_num,G_num,T_num;
A_num=C_num= G_num= T_num=0;
int max;
char str[55][1005] = { 0 };
string dna;
cin >> m;
cin >> n;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cin >> str[j][i];
}
}
for (j = 0; j < n; j++)
{
for (i = 0; i <m; i++)
{
switch (str[j][i])
{
case 'A':A_num++; break;
case 'C':C_num++; break;
case 'G':G_num++; break;
case 'T':T_num++; break;
default:
break;
}
}
max = max_func(A_num, C_num, G_num, T_num);
cout << "MAX=" << max << endl;
if (max == A_num) dna+= 'A';
else if (max == C_num) dna += 'C';
else if (max == G_num) dna += 'G';
else if (max == T_num) dna += 'T';
A_num = C_num = G_num = T_num = 0;
}
cout << dna;
}
运行截图如下：
