260 - Il Gioco dell'X

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

woljako
New poster
Posts: 1
Joined: Sun Sep 21, 2014 9:50 pm

Re: 260 - Il Gioco dell'X

Post by woljako » Sun Sep 21, 2014 9:52 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 260 - Il Gioco dell'X

Post by brianfry713 » Mon Sep 22, 2014 8:49 pm

http://www.udebug.com/UVa/260
Click "Random Input", "Go!"
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 260 - Il Gioco dell'X

Post by uDebug » Fri Apr 03, 2015 7:45 pm

brianfry713,
brianfry713 wrote:http://www.udebug.com/UVa/260
Click "Random Input", "Go!"
Thanks for the great test cases!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Ridowan_Ahmed
New poster
Posts: 1
Joined: Thu Nov 10, 2016 4:46 am

Re: 260 - Il Gioco dell'X

Post by Ridowan_Ahmed » Thu Nov 10, 2016 4:59 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 260 - Il Gioco dell'X

Post by lighted » Mon Mar 13, 2017 3:54 pm

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')
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 2 (200-299)”