习题3.6 纵横字谜的答案 UVa232

1.题目描述：点击打开链接

2.解题思路：本题属于模拟题，按照题意，第一步标记出各个点的起始位置的编号，第二步开始找这些字符串，先横着找，再竖着找。注意时刻都要警惕不要越界。在竖着找的时候由于不一定按照编号大小顺序加入vector，因此最后要再做一次排序。

3.代码：

#define _CRT_SECURE_NO_WARNINGS 
#include
#include
#include
#include
#include
#include
#include
#include
across, down;
int g[N][N];
char gr[N][N];
int r, c;
void mark()//标记起始点的编号
{int cnt = 0;for (int i = 0; i < r;i++)for (int j = 0; j < c; j++){if ((!i || !j)&&gr[i][j]!='*')g[i][j] = ++cnt;else if (gr[i][j]!='*'&&(gr[i - 1][j] == '*' || gr[i][j - 1] == '*'))g[i][j] = ++cnt;}
}
void solve()
{int pos,id;string s;for (int i = 0; i < r; i++)//横着找{int k = 0;while (k < c){while (k < c&&!g[i][k])k++;if (k < c){ id = g[i][k]; s.clear(); }else break;while (k < c&&gr[i][k]!='*') s += gr[i][k++];if (s.length()>0)across.push_back(P(id, s));}}for (int j = 0; j < c; j++)//竖着找{int i = 0;while (i < r){while (i < r&&!g[i][j])i++;if (i < r){ id = g[i][j]; s.clear(); }else break;while (i < r&&gr[i][j] != '*')s += gr[i++][j];if (s.length()>0)down.push_back(P(id, s));}}sort(down.begin(), down.end());
}
int main()
{//freopen("t.txt", "r", stdin);int rnd = 0;while (~scanf("%d", &r)&&r){cin >> c;across.clear(), down.clear();memset(g, 0, sizeof(g));memset(gr, '\0', sizeof(gr));for (int i = 0; i < r; i++)scanf("%s", gr[i]);mark();solve();if (rnd)cout << endl;printf("puzzle #%d:\n", ++rnd);puts("Across");int len = across.size();for (int i = 0; i < len; i++)printf("%3d.%s\n", across[i].first, across[i].second.c_str());puts("Down");len = down.size();for (int i = 0; i < len;i++)printf("%3d.%s\n", down[i].first, down[i].second.c_str());}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！