概述
首先是理解题意，这个刘汝佳写的很明白了，其实就是找1里面包着的有多少个0的连通块，不同的1的块互不干扰不相邻不包含，然后我就看uva上的例子，想把16进制化成2进制然后看是不是对的上，结果硬是对不上号，上面有很多省略的行，弄的我是一头雾水，无奈去uDbug上面复制几个样例，输入转换一下才确定题意就是这么回事，然后开始想题，
一开始硬是想不起来，怎么才能确定一个0连通块是在1里面的，终于想到可以设置一个辅助的数组，一般这种dfs需要两个数组，一个存数据，一个存是否访问，现在我们遍历数组，一旦遇到一个1连通块，我们在dfs的时候，也对设置的辅助数组进行更改，最终辅助数组只有当前这个1连通块，其余都是0，接下来我们就能对两个辅助数组进行第二种dfs，来数0连通块个数的dfs，数出来减一就是结果，
结果还有一个数据点没过，才发现如果一个1连通块里面不含0，但是它和边界相连，是可能造成0的连通块个数不为1，而是23456，，，的情况的，又开始想怎么解决这个，想了两分钟才想到可以设置辅助数组的时候行数+2列数+2，就是在外面填充一圈零，这样原始数组里面不属于1连通块的，但是被1连通块分割的0连通块就连到一起了，只需要减一就行了，然后稍微修改了一下，原始数组里面的0，0位置的放到1，1，以此类推，就可以了，
看看题解的时候学习了另外一种思路，就是找黑色连通块的时候给它做好标记，然后找白色连通块，如果它和边界挨着，也就是递归的时候可以到四个边界，那么它是肯定不被黑色连通块包围的，对剩下的白色连通块dfs，看看递归到的黑色连通块的标记，那么它就是属于这个黑色连通块的，
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int N = 205;
int h, w;
int mat[N][N], vis[N][N], Hash[N][N], vis2[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char str[20] = "WAKJSD";
int rec[20][4] = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1,
1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1};
void dfs(int x, int y) {
vis[x][y] = 1;
Hash[x + 1][y + 1] = 1;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r < 0 || r >= h || c < 0 || c >= w) continue;
if (!vis[r][c] && mat[r][c]) dfs(r, c);
}
}
void dfs2(int x, int y) {
vis2[x][y] = 1;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r < 0 || r >= h + 2 || c < 0 || c >= w + 2) continue;
if (!vis2[r][c] && !Hash[r][c]) dfs2(r, c);
}
}
int main() {
int num = 1;
while (cin >> h >> w && h) {
memset(mat, 0, sizeof(mat));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < h; i++) {
string s;
cin >> s;
for (int j = 0; j < sz(s); j++) {
if (s[j] == '0') continue;
int t;
if (isdigit(s[j])) t = s[j] - '0';
else t = s[j] - 'a' + 10;
for (int k = j * 4; k < j * 4 + 4; k++) {
mat[i][k] = rec[t][k - j * 4];
}
}
}
w *= 4;
vector<char> vec;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (mat[i][j] && !vis[i][j]) {
memset(Hash, 0, sizeof(Hash));
memset(vis2, 0, sizeof(vis2));
int cnt = 0;
dfs(i, j);
for (int ii = 0; ii < h + 2; ii++) {
for (int jj = 0; jj < w + 2; jj++) {
if (!Hash[ii][jj] && !vis2[ii][jj]) {
cnt++;
dfs2(ii, jj);
}
}
}
vec.pb(str[cnt - 1]);
}
}
}
sort(all(vec));
cout << "Case " << num++ << ": ";
for (int i = 0; i < sz(vec); i++) cout << vec[i];
cout << endl;
}
return 0;
}
接下来是补一下之前看的思路，主要就是3个深搜，第一个是遍历黑像素，然后给其上标号，第二个是遍历白像素，给其上标号，同时如果搜索过程中遇到了边界，那么标记一下这个标号，就是具有这个标号的白像素是和边界想连的，第三个是遍历不和边界想连的白像素，这时它一定是包围在某个黑像素之内的，遍历的时候遇到，就记录一下遇到的是哪个标号的黑像素，搜索完之后加一，表明这个黑连通块有白块的个数加一，最后统计结果输出，这个复杂度明显比上一个小，但是20ms比50ms感觉提升不大
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int N = 205;
char str[10] = "WAKJSD";
int h, w, mat[N][N], vis[N][N], vis2[N][N], vis3[N][N], cnt, tot, cur;
int Hash[N * N], rec[N * N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int num[20][4] = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1,
1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1};
void dfs(int x, int y) {
vis[x][y] = cnt;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r < 0 || r >= h || c < 0 || c >= w) continue;
if (mat[r][c] && !vis[r][c]) dfs(r, c);
}
}
void dfs2(int x, int y) {
vis2[x][y] = cnt;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (r < 0 || r >= h || c < 0 || c >= w) { Hash[cnt] = 1; continue; }
if (!mat[r][c] && !vis2[r][c]) dfs2(r, c);
}
}
void dfs3(int x, int y) {
vis3[x][y] = 1;
for (int i = 0; i < 4; i++) {
int r = x + dx[i];
int c = y + dy[i];
if (mat[r][c]) { cur = vis[r][c]; continue; }
if (!vis3[r][c]) dfs3(r, c);
}
}
int main() {
int Case = 1;
while (cin >> h >> w && h) {
for (int i = 0; i < h; i++) {
string s;
cin >> s;
for (int j = 0; j < w; j++) {
for (int k = j * 4; k < j * 4 + 4; k++) {
if (isdigit(s[j])) mat[i][k] = num[s[j] - '0'][k - j * 4];
else mat[i][k] = num[s[j] - 'a' + 10][k - j * 4];
}
}
}
w *= 4;
cnt = 1;
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
memset(Hash, 0, sizeof(Hash));
memset(rec, 0, sizeof(rec));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (mat[i][j] && !vis[i][j]) { dfs(i, j); cnt++; }
}
}
tot = cnt - 1;
cnt = 1;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!mat[i][j] && !vis2[i][j]) { dfs2(i, j); cnt++; }
}
}
memset(vis3, 0, sizeof(vis3));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!mat[i][j] && !vis3[i][j] && !Hash[vis2[i][j]]) { dfs3(i, j); rec[cur]++; }
}
}
vector<char> ans;
for (int i = 1; i <= tot; i++) ans.pb(str[rec[i]]);
sort(all(ans));
cout << "Case " << Case++ << ": ";
for (int i = 0; i < sz(ans); i++) cout << ans[i];
cout << endl;
}
return 0;
}
最后
以上就是眯眯眼嚓茶为你收集整理的UVA1103 古代象形符号 Ancient Messages的全部内容，希望文章能够帮你解决UVA1103 古代象形符号 Ancient Messages所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复