thanks a lot,
i've AC with your test!

My code answers correct to your test cases, but Online Judge is saying W#11, I cannot find any case my solution fails. Can you provide more test cases, pls? And how people find the test case, do they figure it out or is there any way to know?

У меня WA 9 и эти тесты работают

But description says that one of teams must win in one move if we imagine that its their turn
So I think that this test cant be real

I think, there is no cases when crosses win in two moves

Finally I decided to use your way and I got AC.
First of all, I cost tree leafs and then run minimax on the tree.
You did in the same way ?
On the leaf-costing I don't like how I find index for the child nodes. Is there a more beautiful way then in function below:

void costIt( char val=1, char pos = 2 ){
    char res = 0;
    for( char i = 0; i < 3; i++ ){
        if ( !arr[ f_x[ i ] ][ f_y[ i ] ] ){
            arr[ f_x[ i ] ][ f_y[ i ] ] = val;
            res = check();
            if ( res == 0 )
                costIt( val == 1 ? -1 : 1, pos*2+1 );
            else if ( !set[ pos > 10 ? (pos-1)/2 : pos ] ){
                cost[ pos > 10 ? (pos-1)/2 : pos  ] = res;
                set[ pos > 10 ? (pos-1)/2 : pos ] = true;
            }
            arr[ f_x[ i ] ][ f_y[ i ] ] = 0;
            pos++;
        }
    }
}

Edited by author 20.12.2011 10:24

yep! :)

Edited by author 22.03.2009 16:51

VERY THANKS! I'v got AC after your mess!)

Read "Site news". Your test is incorrect, because game is already finished by Noughts.

I had WA 14 too. There is a mistake in my program: one of my functions used the global variables but some of variables shouldn't be global.

Now is AC.

What if:

#OO
OXX
O##

for example?!

Your program will count two winning lines for Ouths and judges win
for them, but it's a draw, isn't it.

>

using System;
using System.Collections;

namespace граф_1
{

    class Class1
    {

        [STAThread]
        static void Main(string[] args)

            {
                //читаем
                int n = int.Parse(Console.ReadLine());
                int m = int.Parse(Console.ReadLine());
                int[,] graf = new int[n,n];
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        graf[i, j] = 0;
                for (int i = 0; i < m; i++)
                {
                    string s = Console.ReadLine();
                    string[] s1 = s.Split(' ');
                    graf[int.Parse(s1[0]) - 1, int.Parse(s1[1]) - 1] = 1;
                    graf[int.Parse(s1[1]) - 1, int.Parse(s1[0]) - 1] = 1;
                }
                //Обходим все вершины
                int[] part = new int[n];
                Queue q = new Queue(n);
                bool[] discovered = new bool[n];
                for (int i = 0; i < n; i++)
                {
                    part[i] = 0;
                    discovered[i] = false;
                }
                part[0] = 1;
                bool b = true;
                //определяем, к какой доле они принадлежат
                q.Enqueue(0);
                discovered[0] = true;
                while(q.Count != 0)
                {
                    int v = (int) q.Dequeue();
                    for(int i = 0; i < n; i++)
                    {
                        if(graf[v,i] == 1)
                        {
                            if (!discovered[i])
                            {
                                discovered[i] = true;
                                q.Enqueue(i);
                            }
                            if (part[i] != part[v])
                                part[i] = -part[v];
                            else
                                b = false;
                        }
                    }
                    if (!b)
                        break;
                }
                if (b)
                {
                    for (int i = 0; i < n; i++)
                        if(part[i]==1)
                            Console.WriteLine(i+1);
                }
                else
                    Console.WriteLine(0);

            }
        }
    }