fork download
copy 
  1. // asdasdasda as dasd 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define REP(a,b,c) for(int a=b;a<c;a++)
  5. #define asd(x)              cout<<__LINE__<<" :: "<<#x<< ": "<<x<<endl;
  6. #define asdf(x, y)          cout<<__LINE__<<" :: "<<#x<< ": "<<x<<" | "<<#y<< ": "<<y<<endl;
  7. #define lb() cout << string(15, =) << endl
  8. typedef pair<int,int> ii;
  9. typedef long long LL;
  10. void scan(); void print(); bool rec(int,int,int);
  11. const int M = 10;
  12. int space[M][M], sum[M][M][2], len[M][M][2], avail[M][M][2], G[M][M], dp[41][1<<M][M], setbit[1<<M], n, m;
  13.  
  14. vector<ii> store;
  15. void brute(int idx){
  16.     if(idx == store.size()) print();
  17.     int x = store[idx].first, y = store[idx].second;
  18.     int mask = avail[x][y][0] & avail[x][y][1];
  19.  
  20.     if(not rec(sum[x][y][0], avail[x][y][0], len[x][y][0]) || not rec(sum[x][y][1], avail[x][y][1], len[x][y][1]))
  21.         return ;
  22.  
  23.     while(mask){
  24.         int high = setbit[mask];
  25.         mask -= (1 << high);
  26.         if(min(sum[x][y][0], sum[x][y][1]) - (high + 1) < 0) return;
  27.         if(not rec(sum[x][y][0] - high - 1, avail[x][y][0] - (1 << high), len[x+1][y][0])) continue;
  28.         if(not rec(sum[x][y][1] - high - 1, avail[x][y][1] - (1 << high), len[x][y+1][1])) continue;
  29.         sum[x+1][y][0] = sum[x][y][0] - high - 1;
  30.         sum[x][y+1][1] = sum[x][y][1] - high - 1;
  31.         avail[x+1][y][0] = avail[x][y][0] - (1 << high);
  32.         avail[x][y+1][1] = avail[x][y][1] - (1 << high);
  33.         G[x][y] = high + 1;
  34.         brute(idx + 1);
  35.     }
  36. }
  37.  
  38. int main(){
  39.     freopen("input.txt", "rt", stdin);
  40.     freopen("output.txt", "wt", stdout);
  41.     memset(dp, -1, sizeof dp);
  42.     scan();
  43.     brute(0);
  44.     return 0;
  45. }
  46.  
  47. bool rec(int sum, int mask, int len){
  48. //    printf("here %d %d %d\n", sum, mask, len);
  49.     int &ret = dp[sum][mask][len];
  50.     if(ret != -1) return ret;
  51.     if(sum == 0 and len == 0) return ret = true;
  52.     if(sum == 0 or len == 0) return ret = false;
  53.  
  54.     REP(i, 0, 9){
  55.         if(sum - i - 1 < 0) break;
  56.         if(mask & (1 << i)){
  57.             if(rec(sum - i - 1, mask - (1 << i), len - 1)) return ret = true;
  58.         }
  59.     }
  60.     return ret = false;
  61. }
  62.  
  63. void scan(){
  64.     cin >> n >> m;
  65.     string str;
  66.     REP(i, 0, M) REP(j, 0, M) 
  67.         avail[i][j][0] = avail[i][j][1] = (1 << 9) - 1;
  68.     REP(i, 0, n) REP(j, 0, m){
  69.         cin >> str;
  70.         if(str == ".....") space[i][j] = true, store.push_back(ii(i, j));
  71.         else{
  72.             if(str[0] != 'X') sum[i+1][j][0] = (str[0] - '0')*10 + (str[1] - '0');
  73.             if(str[3] != 'X') sum[i][j+1][1] = (str[3] - '0')*10 + (str[4] - '0');
  74.         }
  75.     }
  76.  
  77.     for(int i = n - 1; i >= 0; i--) for(int j = m - 1; j >= 0; j--){
  78.         if(space[i][j]){
  79.             len[i][j][0] = 1 + (space[i+1][j] ? len[i+1][j][0] : 0);
  80.             len[i][j][1] = 1 + (space[i][j+1] ? len[i][j+1][1] : 0);
  81.         }
  82.     }
  83.  
  84.  
  85.     REP(mask, 0, (1 << 9)) REP(bit, 0, 9) if(mask & (1 << bit)){
  86.         setbit[mask] = bit;
  87.         break;
  88.     }
  89. }
  90.  
  91. void print(){
  92.     REP(i, 0, n){
  93.         REP(j, 0, m){
  94.             if(space[i][j]) printf("%d", G[i][j]);
  95.             else printf("_");
  96.             printf("%c", (j == m - 1) ? '\n' : ' ');
  97.         }
  98.     }
  99.     exit(0);
  100. }
Success #stdin #stdout 0s 4940KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ylveuG
language:
C++ (gcc 8.3)
created:
9 years 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!