本文主要是介绍1103 - Ancient Messages （UVA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接如下：
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3544
代码如下，我是把每个字拷贝出来再计算它的连通块数量，我看其他人的解法，这一步其实可以省去：
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
const int maxx = 205;
// #define debugint h, w, kase = 0;
char ch;
char image[] = "WAKJSD";
int orig[maxx][maxx], mat[maxx][maxx];
std::map<char, std::string> mp;
int du[] = {1, 0, -1, 0};
int dv[] = {0, 1, 0, -1};std::string trans(int n){std::string temp;for (int i = 0; i < 4; ++i){temp.push_back(n % 2 + '0');n /= 2;}reverse(temp.begin(), temp.end());return temp;
}void dfs(int u, int v){if (u < 0 || u >= h || v < 0 || v >= 4 * w || orig[u][v] == 0){return;}orig[u][v] = 0;mat[u + 1][v + 1] = 1;for (int i = 0; i < 4; ++i){dfs(u + du[i], v + dv[i]);}
}void newdfs(int u, int v){if (u < 0 || u >= h + 2 || v < 0 || v >= 4 * w + 2 || mat[u][v] == 1){return;}mat[u][v] = 1;for (int i = 0; i < 4; ++i){newdfs(u + du[i], v + dv[i]);}
}int calConnected(){int cnt = 0;for (int i = 0; i < h + 2; ++i){for (int j = 0; j < 4 * w + 2; ++j){if (mat[i][j] == 0){++cnt;newdfs(i, j);}}}return cnt - 1;
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endiffor (ch = '0'; ch <= '9'; ++ch){int n = ch - '0';mp[ch] = trans(n);}for (ch = 'a'; ch <= 'f'; ++ch){int n = ch - 'a' + 10;mp[ch] = trans(n);}while (scanf("%d %d\n", &h, &w) == 2 && h && w){std::fill(orig[0], orig[0] + maxx * maxx, 0);for (int i = 0; i < h; ++i){for (int j = 0; j < w; ++j){scanf("%c", &ch);std::string temp = mp[ch];for (int k = 0; k < 4; ++k){orig[i][4 * j + k] = temp[k] - '0';}}getchar();}std::string ans;for (int i = 0; i < h; ++i){for (int j = 0; j < 4 * w; ++j){if (orig[i][j] == 1){std::fill(mat[0], mat[0] + maxx * maxx, 0);dfs(i, j);ans.push_back(image[calConnected()]);}}}sort(ans.begin(), ans.end());printf("Case %d: %s\n", ++kase, ans.c_str());}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}在原图上计算每个字的连通块的解法：
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
const int maxx = 210;
// #define debugint h, w, cnt, kase = 0;
char ch;
char image[] = "WAKJSD";
int orig[maxx][maxx];
std::map<char, std::string> mp;
int du[] = {1, 0, -1, 0};
int dv[] = {0, 1, 0, -1};std::string trans(int n){std::string temp;for (int i = 0; i < 4; ++i){temp.push_back(n % 2 + '0');n /= 2;}reverse(temp.begin(), temp.end());return temp;
}void newdfs(int u, int v){if (u < 0 || u > h + 2 || v < 0 || v > w + 6 || orig[u][v]){return;}orig[u][v] = -1;for (int i = 0; i < 4; ++i){newdfs(u + du[i], v + dv[i]);}
}void dfs(int u, int v){if (u < 0 || u > h + 2 || v < 0 || v > w + 6 || orig[u][v] == -1){return;}if (orig[u][v] == 0){cnt++;newdfs(u, v);return;}orig[u][v] = -1;for (int i = 0; i < 4; ++i){dfs(u + du[i], v + dv[i]);}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endiffor (ch = '0'; ch <= '9'; ++ch){int n = ch - '0';mp[ch] = trans(n);}for (ch = 'a'; ch <= 'f'; ++ch){int n = ch - 'a' + 10;mp[ch] = trans(n);}while (scanf("%d %d\n", &h, &w) == 2 && h && w){std::fill(orig[0], orig[0] + maxx * maxx, 0);for (int i = 1; i <= h; ++i){for (int j = 1; j <= w; ++j){scanf("%c", &ch);std::string temp = mp[ch];for (int k = 0; k < 4; ++k){orig[i][4 * j + k] = temp[k] - '0';}}getchar();}w *= 4;newdfs(0, 0);std::string ans;for (int i = 0; i < h + 2; ++i){for (int j = 0; j < w + 6; ++j){if (orig[i][j] == 1){cnt = 0;dfs(i, j);ans.push_back(image[cnt]);}}}sort(ans.begin(), ans.end());printf("Case %d: %s\n", ++kase, ans.c_str());}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}这篇关于1103 - Ancient Messages （UVA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
