usaco_5_1_2_starry-图的旋转.cpp

usaco自己做的1到5章的代码

/*
PROB: starry
LANG: C++
*/
/*
这道题应该算是比较简单，而且数据比较弱，提交后发现竟然才5组数据~
我做时，先是h*w的枚举，然后对于每个以前没处理过的点，进行floodfill，先都填成*，记录过程中的坐标范围，然后拷贝填充成的图形。
对拷贝后的图形进行check，check函数是对高为ht，宽为hw的图形t，进行90*k度的旋转，检查旋转后的图形是否与已经出现过并存入db中的某图形相同，如果相同，用tt返回查找到的图形在db中的位置。
然后再用floodfill对查找到的图形填成字母即可
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXP 101
struct PICT{
    char s[101][101];
    int h,w;
    char ch;
};
int dir[8][2]={{-1,-1},{-1,1},{1,-1},{1,1},{0,1},{0,-1},{1,0},{-1,0}};
char map[MAXP][MAXP];
PICT db[27];
int h,w,n,hx,hy,lx,ly,cnt=0;
bool check(char a[][101],int ht,int hw,int k,int &tt)
{
    int i,j;
    int th,tw;
    char t[101][101];
	th=ht;
	tw=hw;
    if(k==0)
	for (i = 0; i < ht; i++)
        for (j = 0; j < hw; j++)
			t[i][j]=a[i][j];
    else{
    for (i = 0; i < ht; i++)
        for (j = 0; j < hw; j++)
        {
            if (k == 1) {t[hw - j - 1][i] = a[i][j];        th=hw;   tw=ht;       }
            if (k == 2) t[ht - i - 1][hw - j - 1] = a[i][j];
            if (k == 3) {t[j][ht - i - 1] = a[i][j];        th=hw;    tw=ht;      }
            //if (k == 4) a[i][j] = b[i][n - j + 1];
        }
    }
    bool found,yes=false;
    for(i=0;i<cnt;i++)
    {
        if(db[i].h==th && db[i].w==tw){ // (db[i].h!=tw && db[i].w!=th)) continue;
        found=true;
        for(j=0;j<th;j++){
            for(k=0;k<tw;k++)
            if(t[j][k] != db[i].s[j][k])
            {found=false; break;}
			if(!found) break;
		}
        if(found) {yes=true; tt=i; break;}
		}
    }
    return yes;
}
void floodfill(int x,int y,char fdc,char flc)
{
    map[x][y]=flc;
    if(x<hx) hx=x;
    if(x>lx) lx=x;
    if(y<hy) hy=y;
    if(y>ly) ly=y;
    for(int i=0;i<8;i++)
        if(map[x+dir[i][0]][y+dir[i][1]]==fdc)
            floodfill(x+dir[i][0],y+dir[i][1],fdc,flc);
}
void search()
{
    int i,j,k,ht,wt,tt;
    bool found;
    char t[101][101],s[101][101];
	memset(t,'\0',sizeof(t));
    for(i=0;i<h;i++)
        for(j=0;j<w;j++)
        {
            if(map[i][j]=='1'){
                hx=100; hy=100; lx=0;ly=0;
                floodfill(i,j,'1','*');
            }
			else continue;
            wt=ly-hy+1;
            ht=lx-hx+1;
            for(int aa=0;aa<ht;aa++)
                for(int bb=0;bb<wt;bb++)
                    if(map[hx+aa][hy+bb]=='*') t[aa][bb]='*';
                    else t[aa][bb]='0';
            found=false;
            for(k=0;k<4;k++)
            {
                if(check(t,ht,wt,k,tt))
                {
                    floodfill(i,j,'*',tt+'a');
                    found=true;
                    break;
                }
            }
            if(found) continue;
            memcpy(s,t,sizeof(t));
            for(k=0;k<ht;k++)
                for(tt=0;tt<wt;tt++)
                t[k][tt]=s[k][wt-tt-1];
            found=false;
            for(k=0;k<4;k++)
            {
                if(check(t,ht,wt,k,tt))
                {
                    floodfill(i,j,'*',tt+'a');
                    found=true;
                    break;
                }
            }
            if(found) continue;
            db[cnt].h=ht;
            db[cnt].w=wt;
			floodfill(i,j,'*',cnt+'a');
            memcpy(db[cnt++].s,s,sizeof(s));
        }
}
void printpict()
{
    int i,j;
    ofstream fout("starry.out");
    for(i=0;i<h;i++)
        //for(j=0;j<w;j++)
        fout<<map[i]<<endl;
      //  printf("%s\n",map[i]);
}
int main()
{
    int i,j,k;
    ifstream fin("starry.in");
    fin>>w>>h;
   // getchar();
    for(i=0;i<h;i++)
        //for(j=0;j<w;j++)
        fin>>map[i];
    search();
    printpict();
    return 0;
}