| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
200 行C++,极不清晰,仅供参考#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator