UVa : 201 (Squares)


Title : Squares

Link : http://uva.onlinejudge.org/external/2/201.html

Tricky Lines :

  1. V i j indicates a vertical line in column i which connects 
    the dot in row j to the one below in row j + 1
  2. Output format 

Analysis :

  1. its up to you, how u represent the input square
    what I have done,
    if a spot has a horizontal line, starts from it, then marked ‘H’
    if a spot has a vertical line, starts from it, then marked ‘V’
    if a spot has both line, starts from it, then marked ‘B’
    otherwise, initialize it with ‘.’
  2. So, for the 1st input, char array board [] [] looks like,

    B V H V
    H B B V
    . B . V
    . H H .
  3. Then loop through the whole array.
    If u find a ‘B’ then there is a chance of a square, otherwise not
  4. now check, is there a square of size 1, starting with a ‘B’ marked cell
    then check, is there a square of size 2, starting with same cell
    and so on

Runtime : 0.072s

Critical input :
5
25
H 1 1
V 1 1
H 1 2
H 1 3
H 1 4
V 4 1
V 1 2
V 2 2
H 2 2
H 2 3
V 4 2
H 2 4
V 5 2
H 3 2
H 3 3
H 3 4
V 1 3
V 4 3
H 4 3
V 1 4
V 3 4
V 4 4
H 5 1
H 5 2
H 5 3

2
2
V 2 1
H 2 1

4
17
V 1 1
H 1 1
V 1 2
V 3 2
H 4 3
V 4 1
H 4 1
H 1 2
V 4 2
H 1 3
V 3 1
H 3 3
V 3 3
H 3 1
V 1 3
H 3 2
H 4 2

Critical output :
Problem #1

2 square (s) of size 1

**********************************

Problem #2

No completed squares can be found.

**********************************

Problem #3

1 square (s) of size 2
Solution : 
// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

char board [9 + 3] [9 + 3];
int freq [10 + 2];
int n;

void reset ()
{
    for ( int i = 0; i < 12; i++ ) {
        for ( int j = 0; j < 12; j++ ) board [i] [j] = '.';
    }

    memset (freq, 0, sizeof (freq));
}

void isSquare (int r, int c)
{
    int next_r = r + 1;
    int next_c = c + 1;
    int size = 0;
    bool complete;

    while ( next_r <= n && next_c <= n ) {
        size++;
        complete = true;

        if ( board [next_r - 1] [c] == 'H' || board [next_r - 1] [c] == '.' ) break;
        if ( board [r] [next_c - 1] == 'V' || board [r] [next_c - 1] == '.' ) break;

        for ( int i = c; i < c + size; i++ )
            if ( board [next_r] [i] != 'H' && board [next_r] [i] != 'B' ) complete = false;

        for ( int i = r; i < r + size; i++ )
            if ( board [i] [next_c] != 'V' && board [i] [next_c] != 'B' ) complete = false;

        if ( complete ) freq [size]++;

        next_r++;
        next_c++;
    }
}

int main ()
{
    int cases = 0;
    int asterisk = false;

    while ( scanf ("%d", &n) != EOF ) {
        reset ();

        int m;
        scanf ("%d", &m);
        getchar ();

        char line_info [50];
        char ch;
        int p, q;

        for ( int i = 0; i < m; i++ ) {
            gets (line_info);
            sscanf (line_info, "%c %d %d", &ch, &p, &q);

            if ( ch == 'H' ) {
                if ( board [p] [q] == 'V' ) board [p] [q] = 'B';
                else board [p] [q] = 'H';
            }
            else {
                if ( board [q] [p] == 'H' ) board [q] [p] = 'B';
                else board [q] [p] = 'V';
            }
        }

        for ( int i = 1; i < n; i++ ) {
            for ( int j = 1; j < n; j++ )
                if ( board [i] [j] == 'B' ) isSquare (i, j);
        }

        if ( asterisk ) printf ("\n**********************************\n\n");
        asterisk = true;

        printf ("Problem #%d\n\n", ++cases);

        if ( accumulate (freq, freq + 12, 0) == 0 ) printf ("No completed squares can be found.\n");
        else {
            for ( int i = 1; i < 12; i++ )
                if ( freq [i] ) printf ("%d square (s) of size %d\n", freq [i], i);
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

One thought on “UVa : 201 (Squares)

  1. Amigo yo soy colombiano, mire tu código y pues no me pareció optima tu solución, me gustaría que explicaras mas y compartiéramos código.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s