思路
没想到用哈希QAQ..
我这边的瞎搞思路就是先把所有连通块按一种顺序排序
之后对于每一对连通块,对其中一个连通块按8种顺序:
(x优先, y优先), (x非降序, x非升序), (y非降序, y非升序)
再通过判断对于其中一个连通块在这8种情况下相邻点的距离是否与另一连通块对应相等:
(相邻两点x距离与y距离交换, 不交换), (相邻两点x距离取相反数, 不取), (相邻两点y距离取相反数, 不取)
枚举的8种情况都拆成3个二进制位来表示
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#define pb push_back
#define all(a) (a).begin(), (a).end()
using namespace std;
const int N = 550;
int n, m;
char s[N][N];
int vis[N][N], ok[N];
int dx[] = { -1, 0, 1, 0, -1, -1, 1, 1 }, dy[] = { 0, -1, 0, 1, -1, 1, -1, 1 };
bool cmp(int p, int q, int op) {
if (op) return p < q;
return p > q;
}
struct node {
int x, y, op;
bool operator< (const node& ot) const {
node p = *this, q = ot;
int a = (op & 1), b = (op / 2 & 1), c = (op / 4 & 1);
if (a) swap(p.x, p.y), swap(q.x, q.y);
if (p.x != q.x) return cmp(p.x, q.x, b);
return cmp(p.y, q.y, c);
}
};
int tot;
vector <node> v[N];
void dfs(int x, int y) {
v[tot].pb({x, y, 0});
vis[x][y] = 1;
for (int i = 0; i < 8; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 1 || tx > n || ty < 0 || ty > m) continue;
if (s[tx][ty] == '1' && !vis[tx][ty]) dfs(tx, ty);
}
}
char ch = 'a';
void fil(int p) {
ok[p] = 1;
for (auto nd : v[p])
s[nd.x][nd.y] = ch;
}
bool isok(int p, int q) {
int si = v[p].size();
for (int bi = 0; bi < 8; ++bi) {
int a = (bi & 1), b = (bi / 2 & 1), c = (bi / 4 & 1), flg = 0;
for (int i = 1; i < si; ++i) {
int px = v[p][i].x - v[p][i - 1].x, py = v[p][i].y - v[p][i - 1].y;
int qx = v[q][i].x - v[q][i - 1].x, qy = v[q][i].y - v[q][i - 1].y;
if (a) swap(px, py);
if (b) px = -px;
if (c) py = -py;
if (px != qx || py != qy) {
flg = 1;
break;
}
}
if (!flg) return true;
}
return false;
}
bool check(int p, int q) {
if (v[p].size() != v[q].size()) return false;
for (int i = 0; i < 8; ++i) {
for (auto &nd : v[p]) nd.op = i;
sort(all(v[p]));
if (isok(p, q)) return true;
}
return false;
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (!vis[i][j] && s[i][j] == '1') ++tot, dfs(i, j);
for (int i = 1; i <= tot; ++i) sort(all(v[i]));
for (int i = 1; i <= tot; ++i) {
if (ok[i]) continue;
fil(i);
for (int j = i + 1; j <= tot; ++j)
if (!ok[j] && check(i, j)) fil(j);
++ch;
}
for (int i = 1; i <= n; ++i) printf("%s\n", s[i] + 1);
return 0;
}