SGU 229 Divide and conquer（模拟）-白红宇

SGU 229 Divide and conquer（模拟）

阅读量：5819 次

发布时间：2019-06-18

本文共 2957 字，大约阅读时间需要 9 分钟。

题目链接：

题意：一个01矩阵，将数字1分成两部分，使得其中一部分通过翻转0、90、180、270以及平移可以得到另一部分。

思路：枚举翻转和平移的方式。这样就可以建立起原图和新图的关系，即新图上的位置(i,j)对应原图中的位置(x,y)。可知，现在的位置（i,j）最多可能由原图中一个位置而来，原图中的一个位置(x,y)也最多映射到新图的最多一个位置。然后将原图新图有联系的建立链表，DFS。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define FOR0(i,x) for(i=0;i
                
                 =0;i--)#define DOW1(i,x) for(i=x;i>=1;i--)#define DOW(i,a,b) for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%I64d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%I64d\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(u64 x) {printf("%llu\n",x);}void PR(double x) {printf("%.4lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<
                 
                  <
                  
                   =0&&x
                   
                    p[0]) j=1; if(link[p[i]][p[j]]==1) break; } color[p[i]]=1; for(j=i+1;j<=p[0];j++) color[p[j]]=color[p[j-1]]^1; for(j=i-1;j>=1;j--) color[p[j]]=color[p[j+1]]^1;}int DFS(int u,int pre){ p[++p[0]]=u; visit[u]=1; int i,v; for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(v==pre||visit[v]) continue; return DFS(v,u); } if(p[0]&1) return 0; match(); return 1;}int OK(int a[][N]){ clr(head,-1); clr(color,0); clr(visit,0); clr(d,0); e=0; int i,j; FOR0(i,n) FOR0(j,n) if(a[i][j]!=-1&&g[i][j]&&get(a[i][j])) { Add(a[i][j],incode(i,j)); } int sum=0,x; FOR0(i,n) FOR0(j,n) if(g[i][j]) { sum++; x=incode(i,j); if(visit[x]) continue; if(!d[x]) return 0; p[0]=0; if(!DFS(x,0)) return 0; } int cnt=0; FOR0(i,n) FOR0(j,n) cnt+=color[incode(i,j)]; return cnt*2==sum;}void print(){ puts("YES"); int i,j; FOR0(i,n) { FOR0(j,n) printf("%d",color[incode(i,j)]); puts(""); }}int main(){ RD(n); int i,j,k; FOR0(i,n) FOR0(j,n) scanf("%1d",&g[i][j]); for(i=-n;i<=n;i++) for(j=-n;j<=n;j++) { init(i,j); FOR0(k,4) { if(OK(a)) return print(),0; rotate(a); } } puts("NO"); return 0;}

转载地址：http://wmwdx.baihongyu.com/

你可能感兴趣的文章