Advertisement
Guest User

Untitled

a guest
Dec 17th, 2015
165
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define INF (int)10e6
  4. #define eps 10e-6
  5. #define mp make_pair
  6. #define pb push_back
  7. #define all(t) t.begin(),t.end()
  8. #define LL long long
  9. #define MOD 1000000007
  10. #define x first
  11. #define y second
  12.  
  13.  
  14.  
  15. using namespace std;
  16.  
  17.  
  18. int n;
  19. int a[5000][20];
  20. int pos[5000];
  21. int pw;
  22.  
  23. bool check(int mask1,int mask2){
  24.     mask1=mask1%(pw + 1);
  25.     mask2=mask2%(pw + 1);
  26.     int cnt=0;
  27.     for(int i=0;i<n;++i)
  28.         if(a[mask1][i]!=a[mask2][i])
  29.             cnt++;
  30.     if(cnt==1)
  31.         return true;
  32.     return false;          
  33. }
  34.  
  35.  
  36. bool go(int mask){
  37.     if(mask==pw+1){
  38.         for(int i=1;i<=(1<<n);++i){
  39.             if(!check(i,i+1))
  40.                 return false;
  41.         }
  42.         return true;
  43.        
  44.     }
  45.     a[mask][pos[mask]]=1;
  46.     if(go(mask+1))
  47.         return true;
  48.     a[mask][pos[mask]]=0;
  49.     if(go(mask+1))
  50.         return true;   
  51.     return false;  
  52. }
  53.  
  54. void Print(){
  55.     cout << "YES\n";
  56.     for(int i=1;i<=(1<<n);++i){
  57.         for(int j=0;j<n;++j)
  58.             cout << a[i][j];
  59.         cout << "\n";  
  60.     }
  61. }
  62.  
  63. int main(){
  64.    
  65.     freopen("gray-code.in","r",stdin);
  66.     freopen("gray-code.out","w",stdout);
  67.    
  68.     cin >> n; pw=1<<n;
  69.     for(int i=1;i<=(1<<n);++i){
  70.         string s; cin >> s;
  71.         for(int j=0;j<n;++j){
  72.             if(s[j]=='0')
  73.                 a[i][j]=0;
  74.             else if(s[j]=='1')
  75.                 a[i][j]=1;
  76.             else if(s[j]=='?'){
  77.                 a[i][j]=-1;
  78.                 pos[i]=j;
  79.             }      
  80.         }
  81.     }
  82.     if(go(1)){
  83.         Print();
  84.         return 0;
  85.     }
  86.    
  87.     cout << "NO";
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement