260 – Il Gioco dell’X UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=196

Graphs, graph traversal, dfs, flood fill.

How I did it

• Read the size of the row.
• Read the graph.
• Init dfs_matriz. If an element is equal to be set the value to -1, otherwise 0.
• Traverse dfs_matriz. If an element is equal to -1 call dfs(row, col).
• In the dfs execution. If a cell has -1(not discovered) insert the row into a set.
• When dfs ends, check if the row size is equal to set size. If yes break the loop and set a flag = true(Black wins), otherwise continue with the search.
• Print the result.

Hints

• Always you will have a winner. (The problem description has not another option).

Code

#include <iostream>
#include <cstdio>
#include <set>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
#define  NODES     202
using namespace std;
int  dfs_matriz[NODES][NODES];
char matriz[NODES][NODES];
set<int> mySet;
int  row;

void dfs(int x, int y)
{
    dfs_matriz[x][y] = DFS_BLACK;
    mySet.insert(x);

    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE)
                    dfs(a-1, b);
                if(b-1 >= 0 && dfs_matriz[a-1][b-1] == DFS_WHITE)
                    dfs(a-1, b-1);
            }
            if(a+1 < row)
            {
                if(b+1 < row && dfs_matriz[a+1][b+1] == DFS_WHITE)
                    dfs(a+1, b+1);
                if(dfs_matriz[a+1][b] == DFS_WHITE)
                    dfs(a+1, b);
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE)
                dfs(a,b-1);
            if(b+1 < row && dfs_matriz[a][b+1] == DFS_WHITE)
                dfs(a,b+1);
}

void readGraph(int tam)
{
    string str, data = "";

    for(int x=0; x<tam; x++)
    {
        cin>>str;
        data += str;
    }
    int index = 0;
    for(int x=0; x<row; x++)
        for(int y=0; y<row; y++, index++)
            matriz[x][y] = data[index];
}

void initGraph(char pawn)
{
    for(int x=0; x<row; x++)
        for(int y=0; y<row; y++)
        {
            if(matriz[x][y] == pawn)
               dfs_matriz[x][y] = DFS_WHITE;
            else
                dfs_matriz[x][y] = 0;
        }
}

int main()
{
int casos = 1;
while(scanf("%d", &row))
{
    if(!row)
       break;
    readGraph(row);    bool flag = false;
    initGraph('b');
    for(int a=0; a<row && flag == false; a++)
        for(int b=0; b<row; b++)
        {
            if(dfs_matriz[a][b] == DFS_WHITE)
            {
                mySet.clear();
                dfs(a,b);
                if(mySet.size() == row)
                {
                    flag = true;
                    break;
                }
            }
        }
    if(flag)
       printf("%d B\n", casos++);
    else
        printf("%d W\n", casos++);
}
return 0;
}