Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

200 行C++,极不清晰,仅供参考

Posted by wwwaaannngggrs at 2010-06-15 20:56:28 on Problem 1021
#include <iostream>
#include <vector>
#include <memory>
using namespace std;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
typedef bool arr[105][105];
struct Tcon
{
       int h,w;
       bool map[105][105];
};
Tcon t1,t2,t3,t4;
bool m[105][105],vis[105][105],vis2[105][105],used[12000];
int t,w,h,n,x,y,tot,MAXx,MAXy,MINx,MINy;

vector<Tcon> map1;
Tcon temp;
bool ok (Tcon A,Tcon B)
{
     if ((A.h!=B.h)||(A.w!=B.w)) return false;
     for (int iii=1;iii<=A.w;iii++)
         for (int jjj=1;jjj<=A.h;jjj++)
             if (A.map[iii][jjj]!=B.map[iii][jjj])
                return false;
     return true;
}
void fan1()
{
     memset(t4.map,false,sizeof(t4.map));
    for (int ii=1;ii<=t3.w;ii++)
        for (int jj=1;jj<=t3.h;jj++)
            t4.map[ii][jj]=t3.map[t3.w-ii+1][jj];
    memset(t3.map,false,sizeof(t3.map));
    for (int ii=1;ii<=t3.w;ii++)
        for (int jj=1;jj<=t3.h;jj++)
            t3.map[ii][jj]=t4.map[ii][jj];
}
void fan2()
{
     memset(t4.map,false,sizeof(t4.map));
    for (int ii=1;ii<=t3.w;ii++)
        for (int jj=1;jj<=t3.h;jj++)
            t4.map[ii][jj]=t3.map[ii][t3.h-jj+1];
    memset(t3.map,false,sizeof(t3.map));
    for (int ii=1;ii<=t3.w;ii++)
        for (int jj=1;jj<=t3.h;jj++)
            t3.map[ii][jj]=t4.map[ii][jj];
}
void zhuan()
{
     memset(t4.map,false,sizeof(t4.map));
     for (int ii=1;ii<=t3.h;ii++)
         for (int jj=1;jj<=t3.w;jj++)
             t4.map[ii][jj]=t3.map[jj][t3.h+1-ii];
     swap(t3.h,t3.w);
     memset(t3.map,false,sizeof(t3.map));
     for (int ii=1;ii<=t3.w;ii++)
        for (int jj=1;jj<=t3.h;jj++)
            t3.map[ii][jj]=t4.map[ii][jj];
}
bool equal()
{
     if (!(((t1.h==t2.h) && (t1.w==t2.w))||((t1.h==t2.w) && (t1.w==t2.h))))
        return false;
     if (ok(t1,t2)) return true;
     t3=t1;
     fan1();
     if (ok(t2,t3)) return true;
     fan2();
     if (ok(t2,t3)) return true;
     fan1();
     if (ok(t2,t3)) return true;
     t3=t1;
     for (int REP=1;REP<=3;REP++)
     {
         zhuan();
         if (ok(t2,t3)) return true;
         fan1();
         if (ok(t2,t3)) return true;
         fan2();
         if (ok(t2,t3)) return true;
         fan1();
         if (ok(t2,t3)) return true;
         fan2();
     }
     return false;
}       
bool find(Tcon t)
{
     for (int ii=0;ii<tot;ii++)
     {
         if (!used[ii])
         {
         t1=t;
         t2=map1[ii];
         if (equal()) 
         {
         used[ii]=true;
         return true;
         }
         }
     }
     return false;
}
void calc(int x,int y)
{
     vis2[x][y]=true;
     MAXx=max(MAXx,x);
     MAXy=max(MAXy,y);
     MINx=min(MINx,x);
     MINy=min(MINy,y);
     for (int ii=0;ii<=3;ii++)
     {
         if ((!vis2[x+dir[ii][0]][y+dir[ii][1]]) && (m[x+dir[ii][0]][y+dir[ii][1]]))
            calc(x+dir[ii][0],y+dir[ii][1]);
     }
}
void ff(int x,int y)
{
     vis[x][y]=true;
     temp.map[x-MINx+1][y-MINy+1]=true;
     for (int ii=0;ii<=3;ii++)
     {
         if ((!vis[x+dir[ii][0]][y+dir[ii][1]]) && (m[x+dir[ii][0]][y+dir[ii][1]]))
            ff(x+dir[ii][0],y+dir[ii][1]);
     }
}

int main()
{
    cin>>t;
    for (int tt=1;tt<=t;tt++)
    {
        map1.clear();
        memset(m,false,sizeof(m));
        memset(vis,false,sizeof(vis));
        cin>>w>>h>>n;
            for (int j=1;j<=n;j++)
            {
                cin>>x>>y;
                m[x+1][y+1]=true;
                
            }
        tot=0;
        memset(vis2,false,sizeof(vis2));
        for (int i=1;i<=w;i++)
            for (int j=1;j<=h;j++)
            {
                if ((!vis[i][j]) && m[i][j])
                {
                   MAXx=0,MAXy=0;
                   MINx=200000000,MINy=20000000;
                   tot++;
                   memset(temp.map,false,sizeof(temp.map));
                   calc(i,j);
                   temp.h=MAXy-MINy+1;
                   temp.w=MAXx-MINx+1;
                   ff(i,j);
                   map1.push_back(temp);
                }
            } 
        memset(m,false,sizeof(m));
        memset(vis,false,sizeof(vis));
        memset(vis2,false,sizeof(vis2));
        memset(used,false,sizeof(used));
        for (int j=1;j<=n;j++)
            {
                cin>>x>>y;
                m[x+1][y+1]=true;
                
            }
        bool ans=true;
        for (int i=1;i<=w;i++)
            {
            for (int j=1;j<=h;j++)
            {
                if ((!vis[i][j]) && m[i][j])
                {
                   MAXx=0,MAXy=0;
                   MINx=200000000,MINy=20000000;
                   memset(temp.map,false,sizeof(temp.map));
                   calc(i,j);
                   temp.h=MAXy-MINy+1;
                   temp.w=MAXx-MINx+1;
                   ff(i,j);
                   if (!find(temp)) 
                   {
                                    ans=false;
                                    break;
                   }
                }
                
            }
            if (!ans) break;
            } 
        if (ans) cout<<"YES"<<endl; else cout<<"NO"<<endl;
        
    }
}
    

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator