分析题目
-
判断是否是一个星群【非空的在水平/垂直/对角线方向相邻的点的集合】
可以用DFS/BFS实现 -
判断不同星群之间是否相似【星星数目/形状相同】
数目可以在搜索的时候存储,形状判断是个难点。如何无视方向判断两个星群是否形状相同呢?
形状判断想到的一种暴力做法:在搜索星群的过程中将每个星群对应的所有坐标存储下来【坐标转移到原点处,保证相同坐标参考系】。之后为每个星群生成所有可能的八个相似模板【旋转/翻转】,再去匹配数量相同的星群是否存在相同的模板对。 -
采用字典序标记相似星群为相同字符
贴上代码,中途几次都想放弃,尤其是八种相似的坐标变换,对于算法渣渣来说,写起来真的痛苦。
代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
typedef pair<int, int> PII;
const int N = 110, SS = 510;
int starset[SS]; // 用来存储每个星群内的星星数量
char s[N][N]; // 用来处理输入
int mark[N][N]; // 用来存储模板串
int a[N][N]; // 用来存储操作的矩阵
int w, h;
int id; // 用来存储星群的索引
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
unordered_map<int, vector<vector<int>>> sloc;
unordered_map<int, vector<string>> mod;
unordered_map<int, char> word;
void bfs(int i, int j) //寻找星群
{
// 只对没有搜索过的有星星的点进行宽搜
if (a[i][j] != -1) return;
id ++ ; // 星群计数加1
a[i][j] = id;
starset[id] ++ ;
queue<PII> q;
q.push({i, j});
sloc[id].push_back({i, j});
while (q.size())
{
auto t = q.front();
q.pop();
for (int k = 0; k < 8; k ++ )
{
int x = t.first + dx[k], y = t.second + dy[k];
// 寻找周围相邻元素【在界内/未遍历过的星星】
if (x >= 1 && x <= h && y >= 1 && y <= w && a[x][y] == -1)
{
// 要存储并区分不同的星群【500】仅用字符数组存储不够
q.push({x, y});
a[x][y] = id;
starset[id] ++ ;
sloc[id].push_back({x, y});
}
}
}
}
void pattern(int j, int row, int col, int ca)
{
int xx, yy;
memset(mark, 0, sizeof mark);
string ms;
for (int k = 0; k < sloc[j].size(); k ++ )
{
xx = sloc[j][k][0], yy = sloc[j][k][1];
if (ca == 1)
mark[xx][yy] = 1;
else if (ca == 2)
mark[yy][row - xx - 1] = 1;
else if (ca == 3)
mark[row - xx - 1][col - yy - 1] = 1;
else if (ca == 4)
mark[col - yy - 1][xx] = 1;
else if (ca == 5)
mark[xx][col - yy - 1] = 1;
else if (ca == 6)
mark[yy][xx] = 1;
else if (ca == 7)
mark[row - xx - 1][yy] = 1;
else if (ca == 8)
mark[col - yy - 1][row - xx - 1] = 1;
}
int r = row, c = col;
if (ca == 2 || ca == 4 || ca == 6 || ca == 8) r = col, c = row;
for (int p = 0; p < r; p ++ )
{
for (int q = 0; q < c; q ++ )
ms += '0' + mark[p][q];
ms += '*';
}
mod[j].push_back(ms);
}
bool check(int i, int j)
{
// 判断 starset[i] 和 starset[j] 是否相似
// 判断i星群的坐标模式串是否在j星群的模板集合中
// i和j的八种模板已经以字符串形式存储
// 只需判断能否在mod[j]中找出mod[i]
for (int k = 0; k < 8; k ++ )
if (mod[i][0] == mod[j][k]) return true;
return false;
}
int main()
{
cin >> w >> h;
// 读进字符数组并将元素从字符数组存入整型数组
for (int i = 1; i <= h; i ++ )
for (int j = 1; j <= w; j ++ )
{
cin >> s[i][j];
if (s[i][j] == '0') a[i][j] = 0;
else a[i][j] = -1;
}
// 寻找星群
for (int i = 1; i <= h; i ++ )
for (int j = 1; j <= w; j ++ )
bfs(i, j);
// sloc[1~id] 存储的是每个星群的星星的坐标
// sloc[index][location]
// 为了后续模板匹配方便,先将每个星群的坐标规范化到原点
// 找到最小的x和y坐标,再将所有坐标值减去minx和miny
for (int i = 1; i <= id; i ++ )
{
int minx = 200, miny = 200;
for (int j = 0; j < sloc[i].size(); j ++ )
{
minx = min(minx, sloc[i][j][0]);
miny = min(miny, sloc[i][j][1]);
}
for (int j = 0; j < sloc[i].size(); j ++ )
{
sloc[i][j][0] -= minx;
sloc[i][j][1] -= miny;
}
}
for (int j = 1; j <= id; j ++ )
{
// 建星群的模板库 八个方向
// 需要知道原图像的长c和宽r
// (i, j) -> (j,r-i-1) -> (r-i-1,c-j-1) -> (c-j-1,i)
// (i,c-j-1) -> (j,i) -> (r-i-1,j) -> (c-j-1,r-i-1)
// 先统计长和宽
int col = 1, row = 1;
for (int k = 0; k < sloc[j].size(); k ++ )
{
row = max(row, sloc[j][k][0] + 1);
col = max(col, sloc[j][k][1] + 1);
}
// mod[j][第k个模板]
// 对星群j的每个坐标,都需要将其本身和另外的七个变种存入
// 星群j有sloc[j].size()个坐标
for (int tt = 1; tt <= 8; tt ++ ) pattern(j, row, col, tt);
}
// 匹配相似星群
// starset[1~id] 存储每个星群的星星数量,只有出现相同数量的星星才需匹配
word[0] = '0';
char cha = 'a';
for (int i = 1; i <= id; i ++ )
{
if (word.count(i)) continue; // 当前星群已经标记过
word[i] = cha;
for (int j = i + 1; j <= id; j ++ )
{
if (starset[j] != starset[i]) continue;
// starset[i] 和 starset[j] 的星星数量一致
// 需要判断i和j星群是否是相似星群
if (check(i, j)) // i 和 j是相似星群
word[j] = cha;
}
cha ++ ;
}
// 输出最终结果
for (int i = 1; i <= h; i ++ )
{
for (int j = 1; j <= w; j ++ )
cout << word[a[i][j]];
cout << endl;
}
// for (int i = 1; i <= h; i ++ )
// {
// for (int j = 1; j <= w; j ++ )
// cout << a[i][j] << ' ';
// cout << endl;
// }
// 输出各星群数量
// for (int i = 1; i <= id; i ++ ) cout << starset[i] << ' ';
// cout << endl;
return 0;
}
真的牛🐂