| 记录编号 |
378228 |
评测结果 |
AAAAA |
| 题目名称 |
897.夜空繁星 |
最终得分 |
100 |
| 用户昵称 |
 YGOI_真神名曰驴蛋蛋 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.005 s |
| 提交时间 |
2017-03-03 16:19:42 |
内存使用 |
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 prime_map[25]= {
23,41,71,41,23,
41,83,17,83,41,
71,17,19,17,71,
41,83,17,83,41,
23,41,71,41,23
};*/
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) {
//printf("(%d,%d)\n",x,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) {
//printf("%d:(%d,%d)\n",T,x,y);
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;
//printf("%llu\n",f[c][x][y]);
//F[x][y]%=233333;
}
}
}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 printVector(std::vector<UTYPE>&v) {
std::cout<<"size:="<<v.size()<<std::endl;
for(std::vector<UTYPE>::iterator it=v.begin();it!=v.end();++it) {
std::cout<<*it<<" ";
}printf("\n");
}
void print() {
for(int i=1;i<=N;++i) {
for(int j=1;j<=M;++j) {
printf("%c",draw[i][j]=='\0'?'.':draw[i][j]);
}printf("\n");
}printf("\n");
}
void printKind() {
printf("Kind:\n");
for(int i=1;i<=N;++i) {
for(int j=1;j<=M;++j) {
printf("%c",kind[i][j]==0?'.':kind[i][j]+'0');
}printf("\n");
}printf("\n");
}
void printVis() {
printf("Vis:\n");
for(int i=1;i<=N;++i) {
for(int j=1;j<=M;++j) {
printf("%c",vis[i][j]==0?'.':vis[i][j]+'0');
}printf("\n");
}printf("\n");
}
void printF(int c) {
printf("f[%d]:\n",c);
for(int i=1;i<=N;++i) {
for(int j=1;j<=M;++j) {
printf("%20llu ",f[c][i][j]);
}printf("\n");
}printf("\n");
}
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);
// printF(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]);
//printVector(v);
//printVis();
//printKind();
//print();
}
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;
}