fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void get_ac(){
  5.         int E, W;
  6.         cin>>E>>W;
  7.  
  8.         int x[E][W];
  9.         for(int i = 0; i < E; i++){
  10.                 for(int j = 0; j < W; j++){
  11.                         cin>>x[i][j];
  12.                 }
  13.         }
  14.  
  15.         queue<pair<int,string>> q;
  16.         q.push({0, ""});
  17.  
  18.         map<pair<int,string>, int> dep;
  19.         dep[{0, ""}] = 0;
  20.  
  21.         int ans = INT_MAX;
  22.  
  23.         while(q.size()){
  24.                 auto cur = q.front(); q.pop();
  25.                 int ii = cur.first;
  26.                 string str = cur.second;
  27.  
  28.  
  29. //                cout<<ii<<" "<<str<<" "<<dep[{ii, str}]<<"\n";
  30.                 if(ii == E){
  31.                         ans= min(ans, int(dep[cur] + str.length()));
  32.                         continue;
  33.                 }
  34.                 vector<int> cnt(W, 0);
  35.                 for(char c : str){
  36.                         cnt[c - '0']++;
  37.                 }
  38.                 int next_bad = E;
  39.                 for(int j = ii; j < E; j++){
  40.                         bool bad = 0;
  41.                         for(int k = 0; k < W; k++){
  42.                                 if(cnt[k] != x[j][k]){
  43.                                         bad = 1;
  44.                                         break;
  45.                                 }
  46.                         }
  47.                         if(bad) {
  48.                                 next_bad= j;
  49.                                 break;
  50.                         }
  51.                 }
  52.                 int current_depth= dep[cur];
  53.                 if(dep.find({next_bad, str}) == dep.end()){
  54.                         q.push({next_bad, str}); dep[{next_bad, str}]= current_depth;
  55.                 }
  56.                 if(str.size() < 9){
  57.                         for(int w= 0; w < W; w++){
  58.                                 str += (char)(w + '0');
  59.                                 if(dep.find({ii, str}) == dep.end()){
  60.                                         q.push({ii, str});
  61.                                         dep[{ii, str}]= current_depth + 1;
  62.                                 }
  63.                                 str.pop_back();
  64.                         }
  65.                 }
  66.                 if(str.size()){
  67.                         str.pop_back();
  68.                         if(dep.find({ii, str}) == dep.end()){
  69.                                 q.push({ii, str});
  70.                                 dep[{ii, str}] = current_depth + 1;
  71.                         }
  72.                 }
  73.         }
  74.  
  75.         cout<<ans<<"\n";
  76. }
  77. int main() {
  78.         cin.tie(0);
  79.         cin.sync_with_stdio(0);
  80. //
  81. //
  82.         int T = 1, tc = 1;
  83.         cin>>T;
  84.         while(T--){
  85.                 cout<<"Case #"<<tc++<<": ";
  86.                 get_ac();
  87.         }
  88. }
Success #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 0
https://ideone.com/ygoQ5B
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!