260 - Il Gioco dell'X

[woljako]

Why runtime?

Code: Select all

#include<iostream>
#include <stack>
#include<vector>
#include<cstdio>

using namespace std;
vector<unsigned int>czarne[8100];
    stack<unsigned int>Q;

int k;
int liczbawejsc =0;
int wyjscielicznik = 1;
string a1,b1;
void in(int wiersze) {
    int a,b;
    cin >> a1;
    int licznik = 1;
    for ( int i = 0; i<wiersze-1; i++)
    {
         cin >> b1;
         for ( int n = 0; n<wiersze; n++)
         {
             if(a1[n]=='b')
             {if(a1[n]=='b'&& a1[n+1]=='b')
             {
                  a = licznik;
                  b = licznik +1 ;
                  czarne[a].push_back(b);
                  czarne[b].push_back(a);
                   // cout << a << " " << b << endl;
             }
             if(a1[n]=='b' && b1[n]=='b')
             {
                  a = licznik;
                  b = licznik + wiersze ;
                  czarne[a].push_back(b);
                  czarne[b].push_back(a);
                 // cout << a << " " << b << endl;

             }
              if(a1[n]=='b' && b1[n+1]=='b')
             {
                  a = licznik;
                  b = licznik + wiersze +1 ;
                  czarne[a].push_back(b);
                  czarne[b].push_back(a);
                //  cout << a << " " << b << endl;

             }
             }
             licznik ++;
         }


         a1 = b1;
    }

}

void bfs(int wierzcholek)
{
    int flagab[100000];
    int v,w,k=0,max=0;
     int dupa = 0;
       for ( int a = 0; a<100000; a++)
       {
           flagab[a]=0;
       }
       for ( int u =1; u<=wierzcholek; u++)
       {
            if(!flagab[u])
          {
              flagab[u]=1;
            Q.push(u);

            while(!Q.empty())
            {
                k++;

                v=Q.top();
                Q.pop();

                for(int i=0;i<czarne[v].size();i++)
                {


                   w=czarne[v][i];
                   if(
                      w>((wierzcholek*wierzcholek)-wierzcholek)
                      )
                   {
                       cout << wyjscielicznik << " B" << endl;
                       dupa ++;
                   }
                     if(!flagab[w])
                   {
                       Q.push(w);
                       flagab[w]=1;
                   }
                }
            }
          }

    }

    if(dupa==0)
    {
        cout << wyjscielicznik << " W" << endl;
    }
    dupa = 0;
    wyjscielicznik++;

}
void out()
{
 for(int i=0;i<=16;i++){
        cout<<endl<<i<<"->";

    for(int j=0;j<czarne[i].size();j++)
            cout<<czarne[i][j]<<',';
 }
}


int main() {
    while(cin >> liczbawejsc && liczbawejsc!=0)
    {
        in(liczbawejsc);
        bfs(liczbawejsc);
          while(!Q.empty())Q.pop();

        for ( int i = 0; i<4100; i++)
        {
            czarne[i].clear();
        }

 }
 return 0;
    }

[brianfry713]

http://www.udebug.com/UVa/260
Click "Random Input", "Go!"

[uDebug]

brianfry713,

http://www.udebug.com/UVa/260
Click "Random Input", "Go!"

Thanks for the great test cases!

[Ridowan_Ahmed]

My code pass all the test cases in udebug but I'm getting WA. I've use simple bfs to find the path from row 1 to row N

Code: Select all

#include<bits/stdc++.h>
using namespace std ;
#define MAX 202
char grid[MAX][MAX] ;
bool vis[MAX][MAX] ;
int fx[]={-1,-1,+0,+0,+1,+1};
int fy[]={-1,+0,-1,+1,+0,+1};
int dir = 6 ;
int N ;
bool bfs(int start_row,int start_col)
{
    queue<int> Q ;
    Q.push(start_row) ; Q.push(start_col) ;
    while(!Q.empty())
    {
        int cur_row = Q.front() ; Q.pop() ;
        int cur_col = Q.front() ; Q.pop() ;
        for(int i=0 ; i<dir ; i++)
        {
            int x = cur_row + fx[i] ;
            int y = cur_col + fy[i] ;
            if(x>0 && x<=N && y>0 && y<=N && grid[x][y]=='b' && !vis[x][y])
            {
                if(x==N)
                    return true ;
                vis[x][y] = true ;
                Q.push(x) ; Q.push(y) ;
            }
        }
    }
    return false ;
}
void takeInput(int row, int col)
{
    for(int i=1 ; i<=row ; i++)
    {
        for(int j=1 ; j<=col ; j++)
        {
            char ch = getchar() ;
            grid[i][j] = ch ;
        }
        getchar() ;
    }
}
int main()
{
//    freopen("input.txt","r",stdin) ;
//    freopen("output.txt","w",stdout) ;
    int cs=1 ;
    while(scanf("%d",&N) && N!=0)
    {
        getchar() ;
        takeInput(N,N) ;
        memset(vis,false,sizeof vis) ;
        bool blackWIn = false ;
        for(int i=1 ; i<=N ; i++)
        {
            if(grid[1][i]!='b')
            {
                vis[1][i] = true ;
                blackWIn = bfs(1,i) ;
                if(blackWIn)
                    break ;
                memset(vis,false,sizeof vis) ;
            }
        }
        if(blackWIn)
            printf("%d B\n",cs++) ;
        else
            printf("%d W\n",cs++) ;
    }
    return 0 ;
}

[lighted]

I checked your code and found one line little strange. Before starting bfs you check if field is not black, but in your bfs you check if field is black. I think both checks should be same, i.e. both should be black. Because you check if black wins. Following line

Code: Select all

if(grid[1][i]!='b')

Should be

Code: Select all

if(grid[1][i]=='b')