fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define F first
  5. #define S second
  6. #define loop(a,n) for(int i=a; i<=n ; i++)
  7. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  8. #define NAME ""
  9. using namespace std;
  10.  
  11. int m,n;
  12. int a[105][105];
  13. int res[105][105];
  14. bool found = false;
  15.  
  16. int dx[] = {-1,1,0,0};
  17. int dy[] = {0,0,-1,1};
  18.  
  19. bool val(int x,int y) {
  20.     return x>=1 && x<=m && y>=1 && y<=n;
  21. }
  22. int dem(int i,int j) {
  23.     int cnt=0;
  24.     for (int d=0;d<4;++d) {
  25.         int ni=i+dx[d];
  26.         int nj=j+dy[d];
  27.         if (val(ni,nj) && res[ni][nj]==1)
  28.             cnt++;
  29.     }
  30.     return cnt;
  31. }
  32. bool check() {
  33.     for(int i=1;i<=m;++i)
  34.         for(int j=1;j<=n;++j)
  35.             if (dem(i,j) != a[i][j])
  36.                 return false;
  37.     return true;
  38. }
  39. void backtrack(int i,int j) {
  40.     if (found) return;
  41.     if (i==m+1) {
  42.         if (check()) {
  43.             found = true;
  44.         }
  45.         return;
  46.     }
  47.     int ni=i, nj=j+1;
  48.     if (nj==n+1) {
  49.         ni=i+1;
  50.         nj=1;
  51.     }
  52.  
  53.     res[i][j]=0;
  54.     backtrack(ni,nj);
  55.     if (found) return;
  56.     res[i][j]=1;
  57.     backtrack(ni,nj);
  58.     if (found) return;
  59. }
  60. void nhap(){
  61.     cin>>m>>n;
  62.     for(int i=1;i<=m;++i)
  63.         for(int j=1;j<=n;++j)
  64.             cin >> a[i][j];    
  65. }
  66. void solve(){
  67.     backtrack(1,1);
  68.     if (!found) cout<<0;
  69.     else {
  70.         cout<<1<<endl;
  71.         for(int i=1;i<=m;++i) {
  72.             for(int j=1;j<=n;++j)
  73.                 cout<<res[i][j] << ' ';
  74.             cout<<endl;
  75.         }
  76.     }
  77. }
  78. int main(){
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0);cout.tie(0);
  81.     //freopen(NAME".INP","r",stdin);
  82.     //freopen(NAME".OUT","w",stdout);
  83.     nhap();
  84.     solve();
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/r3YBSD
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!