记录编号	117247	评测结果	AAAAA
题目名称	夜空繁星	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-08-29 08:22:35	内存使用	0.36 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct points
{
  int x,y,nowx,nowy;
  points(int x,int y,int nowx,int nowy):x(x),y(y),nowx(nowx),nowy(nowy){};
  points(){};
  bool operator <(const points rhs) const
  {
    return x<rhs.x||(x==rhs.x&&y<rhs.y);
  }
};
struct stars
{
  int len;//以左上角为(1,1)建立平面直角坐标系,该平面直角坐标系是[1,len] 
  vector <points> hoshi;//记录该星座内的星星的位置 
  stars()
  {
    this->len=0;
  }
  //顺时针旋转 
  void rotate()
  {
    //原来在 (a,b) 的点旋转到(len+1-b,a)点
    vector <points> news;
    news.clear();
    int siz=hoshi.size()-1;
    For(i,0,siz)
    {
      points p;
      p.x=len+1-hoshi[i].y;
      p.y=hoshi[i].x;
      p.nowx=hoshi[i].nowx;
      p.nowy=hoshi[i].nowy;
      news.push_back(p);
    }
    this->hoshi=news;
    return ;
  } 
  //镜面对称 
  stars mirror() const
  {
    stars res=(*this);
    vector <points> news;
    news.clear();
    int siz=hoshi.size()-1;
    For(i,0,siz)
    {
      points p;
      p.x=len+1-hoshi[i].x;
      p.y=hoshi[i].y;
      p.nowx=hoshi[i].nowx;
      p.nowy=hoshi[i].nowy;
      news.push_back(p);
    }
    res.hoshi=news;
    return res;
  }
  //切记比较前先将星星排序！！！！ 
  bool operator ==(const stars rhs) const
  {
    int siz=rhs.hoshi.size()-1;
    if (hoshi.size()!=siz+1) return false;
    int deltax=hoshi[0].x-rhs.hoshi[0].x;
    int deltay=hoshi[0].y-rhs.hoshi[0].y;
    For(i,1,siz)
      if (hoshi[i].x-rhs.hoshi[i].x!=deltax||hoshi[i].y-rhs.hoshi[i].y!=deltay)
        return false;
    return true;
  }
};//记录单个星座 
//==============var declaration=================
bool star[150][150];//是否有星星+bfs访问标记 
char color[150][150];
int sx,sy;
int mvx[]={-1,-1,-1,0,0,1,1,1};
int mvy[]={-1,0,1,1,-1,1,0,-1};
vector <stars> book;//记录已经检测出的星座 
//==============function declaration============
void dfs(int nowx,int nowy,int x,int y,stars &save); 
void mark(stars &x);
//==============main code=======================
int main()
{  
  string FileName="starry";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  //读入星体图 +初始化 
  scanf("%d%d",&sx,&sy);
  char chs[500];
  char ch;
  cin.ignore(10,10);
  for(int i=1;i<=sy;i++)
  {
    cin.getline(chs,160);
    for(int j=1;j<=sx;j++)
    {
      ch=chs[j-1];
      if (ch=='0')
        star[j][i]=false;
      else if (ch=='1')
        star[j][i]=true;
      else
      {
        printf("Init Error!\n");
        return 0;
      }
    }
  }
  //寻找相同的星座
  book.clear();
  For(j,1,sy)
    For(i,1,sx) 
    {
      if (star[i][j])
      {
        stars p;
        star[i][j]=false;
        dfs(i,j,1,1,p);//bfs函数分理出星座 
        mark(p);//mark函数将p星座与之前星座进行对比并编号 
      }
    }
  //输出
  For(j,1,sy)
  {
    For(i,1,sx)
      if (color[i][j]>='a'&&color[i][j]<='z')
        printf("%c",color[i][j]); 
      else
        printf("0");
    printf("\n");
  }
  
   
#ifdef DEBUG  
  clock_t End_Time=clock();
  printf("\n\nTime Used: %.3lf\n",End_Time-Start_Time);
#endif    
  return 0;
}
//================fuction code====================
void dfs(int nowx,int nowy,int x,int y,stars &save)
{
   int xx,yy;
   save.hoshi.push_back(points(x,y,nowx,nowy));
   if (x>save.len||y>save.len)
     save.len=max(x,y); 
   For(i,0,7)
   {
     xx=nowx+mvx[i];
     yy=nowy+mvy[i];
     if ((xx<1||xx>sx||yy<1||yy>sy)||(!star[xx][yy])) continue;
     star[xx][yy]=false;
     dfs(xx,yy,x+mvx[i],y+mvy[i],save);
   }
   return ;
}//分离单个星座，保存于save中 
void mark(stars &x)
{
  int m=book.size()-1;
  int t=x.hoshi.size()-1;
  For(i,0,m)
    if (t==book[i].hoshi.size()-1)
    {
      sort(book[i].hoshi.begin(),book[i].hoshi.end());
      For(j,1,4)
      {
        x.rotate();
        sort(x.hoshi.begin(),x.hoshi.end());
        if (x==book[i])
        {
          For(k,0,t)
            color[x.hoshi[k].nowx][x.hoshi[k].nowy]=i+'a';
          return; 
        }
      };
      stars p=x;
      For(j,1,4)
      {
        p.rotate();
        x=p.mirror();
        sort(x.hoshi.begin(),x.hoshi.end());
        if (x==book[i])
        {
          For(k,0,t)
            color[x.hoshi[k].nowx][x.hoshi[k].nowy]=i+'a';
           return; 
        }
      }
    } 
  book.push_back(x);
  For(j,0,t)
    color[x.hoshi[j].nowx][x.hoshi[j].nowy]=m+1+'a'; 
  return;
}