记录编号	378229	评测结果	AAAAA
题目名称	夜空繁星	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-03-03 16:21:23	内存使用	0.60 MiB

#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef unsigned long long UTYPE;
const int move[8][2]={
		{-1,-1},{-1,+0},{-1,+1},
		{+0,-1},        {+0,+1},
		{+1,-1},{+1,+0},{+1,+1}
	};
const int prime_map[25]= {
	56527,99991,26321,99991,56527,
	99991,31189,45007,31189,99991,
	26321,45007,87959,45007,26321,
	99991,31189,45007,31189,99991,
	56527,99991,26321,99991,56527
};
const int step[25][2]= {
		{-2,-2},{-2,-1},{-2,+0},{-2,+1},{-2,+2},
		{-1,-2},{-1,-1},{-1,+0},{-1,+1},{-1,+2},
		{+0,-2},{+0,-1},{+0,+0},{+0,+1},{+0,+2},
		{+1,-2},{+1,-1},{+1,+0},{+1,+1},{+1,+2},
		{+2,-2},{+2,-1},{+2,+0},{+2,+1},{+2,+2},
	};
const int MAXN=110;
int N,M;
int vis[MAXN][MAXN];
int kind[MAXN][MAXN];
char draw[MAXN][MAXN];
UTYPE f[2][MAXN][MAXN];
std::map<std::vector<UTYPE>,char>hash;
#define xx (x+move[ic][0])
#define yy (y+move[ic][1])
void dfs1(int x,int y) {
	kind[x][y]=2;
	for(int ic=0;ic<8;++ic) {
		if(xx>=1&&xx<=N&&yy>=1&&yy<=M) {
			if(kind[xx][yy]==1) {
				dfs1(xx,yy);
			}
		}
	}
}
#define xh (x+step[ic][0])
#define yh (y+step[ic][1])
void dfs2(int x,int y,int T,bool c) {
	vis[x][y]=T;
	UTYPE v=0;
	for(int ic=0;ic<25;++ic) {
		if(xh>=1&&xh<=N&&yh>=1&&yh<=M) {
			if(kind[xh][yh]==2) {
				v+=f[c][x][y]*prime_map[ic];
				v+=f[c^1][xh][yh]+1;
			}
		}
	}f[c][x][y]+=v;
	for(int ic=0;ic<8;++ic) {
		if(xx>=1&&xx<=N&&yy>=1&&yy<=M) {
			if(vis[xx][yy]!=T&&kind[xx][yy]==2) {
				dfs2(xx,yy,T,c);
			}
		}
	}
}
void dfs3(int x,int y,int T,std::vector<UTYPE>&v) {
	vis[x][y]=T;
	v.push_back(f[0][x][y]);
	for(int ic=0;ic<8;++ic) {
		if(xx>=1&&xx<=N&&yy>=1&&yy<=M) {
			if(vis[xx][yy]!=T&&kind[xx][yy]==2) {
				dfs3(xx,yy,T,v);
			}
		}
	}
}
void dfs4(int x,int y,char c) {
	draw[x][y]=c;
	kind[x][y]=3;
	for(int ic=0;ic<8;++ic) {
		if(xx>=1&&xx<=N&&yy>=1&&yy<=M) {
			if(kind[xx][yy]==2) {
				dfs4(xx,yy,c);
			}
		}
	}
}
void search(int x,int y) {
	const int UPLOAD=9;
	static char seq='a';
	std::vector<UTYPE>v;
	dfs1(x,y);
	for(int T=1;T<UPLOAD;++T) {
		dfs2(x,y,T,T&1);
	}dfs3(x,y,UPLOAD,v);
	std::sort(v.begin(),v.end());

	if(hash.count(v)==0){
		hash[v]=seq++;
	}
	dfs4(x,y,hash[v]);
}
int main() {
	freopen("starry.in","r",stdin);
	freopen("starry.out","w",stdout);
	scanf("%d%d",&M,&N);
	for(int i=1;i<=N;++i) {
		for(int j=1;j<=M;++j) {
			scanf("%1d",&kind[i][j]);
		}
	}
	for(int i=1;i<=N;++i) {
		for(int j=1;j<=M;++j) {
			if(kind[i][j]==1)
				search(i,j);
		}
	}
	for(int i=1;i<=N;++i) {
		for(int j=1;j<=M;++j) {
			printf("%c",draw[i][j]=='\0'?'0':draw[i][j]);
		}printf("\n");
	}fclose(stdin);fclose(stdout);
	return 0;
}