Что ненужного я добавил в функцию DFS? Значение больше, чем ожидалось - PullRequest
Новая
       65

Что ненужного я добавил в функцию DFS? Значение больше, чем ожидалось

0 голосов
/ 02 ноября 2019

'' 'в этой проблеме онлайн-судьи - это пространство, которое необходимо заполнить буквой' O 'или' X '. Я использую DFS для решения этой проблемы.

Но вывод, который я получаю из этого кода, намного больше, чем ответ, особенно когда много «-». Как это исправить? 

int O=0,X=0,Tie=0,T=0,VX=0,VO=0;
set<string>U;
void DFS(string s)
{
    if(U.find(s)==U.end()) 
    {
        U.insert(s);
        T=0;
        VX=0;
        VO=0;
        string c;
        for(int i=0;i<9;i++) if(s[i]=='-') T=1;
        for(int i=0;i<3;i++)
        {
            if(s[i]=='O'&&s[i+3]=='O'&&s[i+6]=='O') VO=1;
            if(s[i]=='X'&&s[i+3]=='X'&&s[i+6]=='X') VX=1;
            if(s[i*3]=='O'&&s[i*3+1]=='O'&&s[i*3+2]=='O') VO=1;
            if(s[i*3]=='X'&&s[i*3+1]=='X'&&s[i*3+2]=='X') VX=1;
        }
        if(s[0]=='O'&&s[4]=='O'&&s[8]=='O') VO=1;
        if(s[0]=='X'&&s[4]=='X'&&s[8]=='X') VX=1;
        if(s[2]=='O'&&s[4]=='O'&&s[6]=='O') VO=1;
        if(s[2]=='X'&&s[4]=='X'&&s[6]=='X') VX=1;
        if(VO) O++;
        else if(VX) X++;
        else if((!T)&&(!VO)&&(!VX)) Tie++;
        else
        {
            for(int i=0;i<9;i++)
            {
                c=s;
                if(c[i]=='-')
                {
                    c[i]='O';
                    DFS(c);
                    c[i]='X';
                    DFS(c);
                }
                c=s;
            }  
        }  
    }
}
int main() 
{
  int n;
  cin>>a;
  DFS(a);
  cout<<O+X+Tie<<" "<<O<<" "<<X<<" "<<Tie<<"\n";
  return 0;
}

Пример ввода # 1

OX - X-XOO

Пример вывода # 1

4 1 21

Ответ, который я получил # 1

14 3 10 1

Пример ввода # 2

O-OXO-X -

Пример вывода # 2

11 9 1 1

Ответ Я получил # 2

41 33 6 2

Пример ввода # 3

O-OXO-XX

Пример вывода # 3

4 2 1 1

Ответ Я получил # 3

14 6 6 2

...