Friday, January 15, 2016

Facebook Hacker Cup 2014 Qualification Round, Square Detector

Problem statement:
https://www.facebook.com/hackercup/problem/318555664954399/

Solution:
We scan all cells started from the first row, from left to right for each row.
When the first black cell found, save the position as x0 and y0.
If there is indeed a valid black square, the position (x0,y0) will be the left-top corner of the black square.
During scanning we also count the black cells and the maximum x and y position of the black cell. We save these values as cnt_Black_Cells, maxX, and maxY.

After finished, we need to verify that the width of the candidate of the black square is black_width = (maxX - x0 + 1). It must be equal to (maxY - y0 +1), otherwise it is not a square.
The value of cnt_Black_Cells should also equal to black_width * black_width.

Then we scan the cells again, but now we only need to scan the following area:
 y: y0 to maxY 
 x: x0 to maxX
During this scan, we verify that every cell in this region is black.
If we found any white cell, then it is not a valid square.

Example codes:

            int T = inp.NextInt ( );
            //int T=1;

            for ( int t = 0; t < T; t++ )
            {
                int N = inp.NextInt ( );
                int x0=-1;
                int y0=-1;
                int xMax=-1;
                int yMax=-1;
                char[][] grid = new char[N][];
                for ( int i = 0; i < N; i++ )
                {
                    string s = inp.NextString ( );
                    grid[i] = s.ToCharArray ( );
                }
                int numBlacks=0;
                for ( int i = 0; i < N; i++ )
                {
                    for ( int j = 0; j < N; j++ )
                    {
                        if ( grid[i][j] == '#' )
                        {
                            if ( x0 < 0 )
                                x0 = j;
                            if ( y0 < 0 )
                                y0 = i;
                            xMax = Math.Max ( xMax, j );
                            yMax = Math.Max ( yMax, i );
                            numBlacks++;
                        }
                    }
                }
                int nb=0;
                for ( int i = y0; i <= yMax; i++ )
                {
                    for ( int j = x0; j <= xMax; j++ )
                    {
                        if ( grid[i][j] == '#' )
                            nb++;
                    }
                }
                int dy = yMax - y0 + 1;
                int dx = xMax - x0 + 1;
                string ans=( ( dx == dy ) && ( numBlacks == nb ) && ( dx * dx == nb ) ) ? "YES" : "NO";
                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
    }

No comments:

Post a Comment