使用不良ユーザー[2019 KACA冬季便利]C+DFS Setのプール

4953 ワード
テキストリンク
最初は単純にfor文で徹底的に探索すれば問題を解決できると思っていた.しかし、よく考えてみると、user idと無効idの総数は8つ以下です.
多重for文では総数を求めることができません.
したがって,Brootforceで解くにはDFSを適用する必要がある.
2つ目のテストケースを例にとります.

user idのインデックスは0～4、idを無効にしたインデックスは0～2です.
したがって
user idのインデックスidを無効にするインデックス
012 0 1 2
013 0 1 2
014 0 1 2
023 0 1 2
024 0 1 2
034 0 1 2
021 0 1 2
023 0 1 2
...
102 0 1 2
このようにして.
同じ文字列かどうかを確認します.
*を除いて、誰もが同じ文字列なのか砲口なのかをチェックします.
user idの014 frodo fradi frodocがrodo rodo**と同じかどうかを確認します.
李慶宇は違います.
もしその3つが同じなら、ベクトルtemp;に入る
次にsを設定してベクトルを繰り返しチェックします.に入る
setにこのベクトルがない場合、ベクトルの個数は1です.
setにこのベクトルがある場合、繰り返しである場合、状況の数は増加しません.
これによりsetsで重複検査を行うと,正解が容易に得られる.
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
vector <string> uid;
vector <string> bid;
int usize; int bsize;
int visited[8]={0,};
set <vector <string> > s;
vector <int> v;
int answer=0;

bool isSame(string a, string b)
{
  if(a.size()!=b.size())
      return false;
  bool isFalse=0;
  for(int i=0;i<a.size();i++)
  {
      if(b[i]=='*') continue;
      if(a[i]!=b[i])
      {
          isFalse=1;
          break;
      }
  }
  if(isFalse==1) return false;
  return true;
}

void dfs() {

  if(v.size()==bsize)
  {
      bool isAnswer=1;
      
      for(int i=0;i<v.size();i++)
          if(!isSame(uid[v[i]],bid[i]))
          {
           isAnswer=0;
              break;
          }
      
      if(isAnswer==1)
      {
          vector <string> temp;
          
          for(int i=0;i<v.size();i++)
              temp.push_back(uid[v[i]]);
          
          sort(temp.begin(),temp.end());
          
          if(s.find(temp)==s.end())
          {
              answer++;
              s.insert(temp);
          }
      }
      return;
  }
  
  for(int i=0;i<usize;i++)
  {
      if(visited[i]!=0) continue;
      visited[i]=1;
      v.push_back(i);
      dfs();
      v.pop_back();
      visited[i]=0;
  }
}

int solution(vector<string> user_id, vector<string> banned_id) {
  uid=user_id; bid=banned_id;
  usize=uid.size(); bsize=bid.size();
  dfs();
  return answer;
}
[BOJ]7576. 名トマト
Javascript_30_01_02