OJ Board

Code: Select all

#include <iostream>
#include <stdio.h>

using namespace std;

#ifdef ONLINE_JUDGE
 #define Fin stdin
 #define Fout stdout
#else
 #define Fin f1
 #define Fout f2
#endif

int countSquares[90];
int H[90][80]; //Horizontal pieces just a 0 or a 1
int V[80][90]; //Vertical pieces just a 0 or a 1

int n; //number of dots

//check for a square starting at row,col and size "size"
char checkSquare(int size,int row,int col)
{
  if(row+size>=n) return 0;
  if(col+size>=n) return 0;
  
//upper horizontal part
  for(int i=0;i<size;i++)
   if(!H[row][col+i])
    return 0;

//lower horizontal part
   for(int i=0;i<size;i++)
   if(!H[row+size][col+i])
    return 0;

//right vertical part
  for(int i=0;i<size;i++)
   if(!V[row+i][col])
    return 0;
//left vertical part    
  for(int i=0;i<size;i++)
   if(!V[row+i][col+size])
    return 0;

   return 1;
}

int main(void)
{
#ifndef ONLINE_JUDGE
  FILE* f1=fopen("squares.in","r");
  FILE* f2=fopen("squares.out","w");
#endif
  int nEdges;
  int probNo=0;
  while(1)
  {
   probNo++;
    if(fscanf(Fin,"%d\n%d\n",&n,&nEdges)!=2)
     break;
   if(probNo!=1)
   fprintf (Fout,"\n**********************************\n\n");

   //reset edges
    for(int i=0;i<=n;i++)
     for(int j=0;j<=n;j++)
     {
      H[i][j]=0;
      V[i][j]=0;
     }
     //reset square counter
      for(int j=0;j<=n;j++)
       countSquares[j]=0;
     
     for(int i=0;i<nEdges;i++)
     {
      char c;
      fscanf(Fin," %c",&c);
      if(c=='H'||c=='h')
      {
       int x,y;
       fscanf(Fin,"%d %d\n",&x,&y);
       H[x-1][y-1]=1;
     }
      else if(c=='V'||c=='v')
      {
       int x,y;
       fscanf(Fin,"%d %d\n",&x,&y);
       V[y-1][x-1]=1;
      }
      else
       while(1); //just to make sure the problem with the code is not an input problem. If there is a problem with the input, the program will fall in an infinte loop. (This doesn't happen)
     }


      for(int j=1;j<=n;j++)
      {
        for(int k=0;k<n;k++)
         for(int m=0;m<n;m++)
           if(checkSquare(j,k,m)) //check for all squares of all sizes
             countSquares[j]++;
      }

      char found=0;
      fprintf(Fout,"Problem #%d\n\n",probNo);
      for(int i=1;i<=n;i++)
       if(countSquares[i])
       {
        fprintf(Fout,"%d square (s) of size %d\n",countSquares[i],i);
        found=1;
       }

       if(!found)
        fprintf(Fout,"No completed squares can be found.\n");

      

  }
 #ifndef ONLINE_JUDGE
 fclose(Fin);
 fclose(Fout);
 #endif

  return 0;
}

Code: Select all

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1

Code: Select all

Problem #1

2 square (s) of size 1
1 square (s) of size 2

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

Problem #2

No completed squares can be found.

Code: Select all

problem #1

3 square (s) of size 1
1 square (s) of size 2

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

problem #2

No completed squares can be found.

Code: Select all

#include<stdio.h>
bool flagH [ 10 ] [ 10 ], flagV[ 10 ] [ 10 ];

void init( int n )
{
    int i, j;
    for(i = 1; i <= n; i ++ )
    {
        for( j = 1; j <= n; j ++)
        {
            flagH [ i ][ j ] = false;
            flagV [ i ][ j ] = false;
        }
    }
    return;
}
bool isValid( int n, int r, int c )
{
    if( r > 0 && r <= n && c > 0 && c <= n )
    {
        return true;
    }
    return false;
}

bool isVcon( int a, int b, int c, int d )
{
    int i, j;

    for( i = a; i <= c; i ++)
    {
        for( j = b; j <= d; j ++)
        {
            if( !flagV [ i ][ j ] )
            {
                return false;
            }
        }
    }
    return true;;
}

bool isHcon( int a, int b, int c, int d )
{
    int i, j;

    for( i = a; i <= c; i ++)
    {
        for( j = b; j <= d; j ++)
        {
            if( !flagH [ i ][ j ] )
            {
                return false;
            }
        }
    }
    return true;;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m, i, row, col, unit, j, count, kase = 1, a = 0;
    char str [ 100 ], c;
    bool print;

    while( gets( str ) )
    {
        if( a )
        {
            printf("\n**********************************\n\n");
        }
        a = 1;
        sscanf(str, "%d", &n);
        gets( str );
        sscanf(str, "%d", &m);

        printf("Problem #%ld\n\n", kase ++);

        init( n );

        for( i = 0; i < m; i ++)
        {
            gets( str );
            sscanf(str, "%c %d %d", &c, &row, &col);
            if( c == 'H' )
            {
                if( isValid ( n, row, col ) && isValid(n, row, col + 1 ))
                {
                    flagH [ row ][ col ] = true;
                    flagH [ row ][ col  + 1 ] = true;
                }
            }
            else
            {
                int temp = row;
                row = col;
                col = temp;

                if( isValid ( n, row, col ) && isValid(n, row + 1, col ))
                {
                    flagV [ row ][ col ] = true;
                    flagV [ row + 1 ][ col ] = true;
                }
            }
        }

        //unit = 1;
        print = false;

        for( unit = 1; unit <= n; unit ++)
        {
            count = 0;
            for( i = 1; i <= n; i ++)
            {
                for( j = 1; j <= n; j ++ )
                {
                    if( isValid( n, i, j + unit ) && isValid( n, i + unit , j) && isValid( n, i + unit, j + unit ))
                    {
                        //printf("%ld\n", unit);
                        if( isVcon( i, j , i + unit, j ) && isHcon(i, j, i, j + unit)
                        && isHcon( i + unit, j, i + unit, j + unit ) && isVcon( i, j + unit, i + unit, j + unit)
                        )
                        {
                            //printf("%d %d\n", i, j);
                            count ++;
                        }
                    }
                }
            }
            if( count > 0 )
            {
                print = true;
                printf("%d square (s) of size %d\n", count, unit);
            }
        }
        if( !print )
        {
            printf("No completed squares can be found.\n");
        }
    }

    return 0;
}

Code: Select all

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main {
	
	static void main(String[] argv)
	{
		begin();
	}
	
	static void begin()
	{
		int nProblem = 1;
		int width, nEdges;
		
		String sBuf;
		int xBuf, yBuf;
		
		Scanner stdin = new Scanner(System.in);
		while (stdin.hasNext())
		{
			width = stdin.nextInt();
			nEdges = stdin.nextInt();
			
			MeshGrid grid = new MeshGrid(width - 1, width - 1);
					
			for (int i = 0; i < nEdges; i++)
			{
				sBuf = stdin.next();
				xBuf = stdin.nextInt() - 1;
				yBuf = stdin.nextInt() - 1;
				
				if (sBuf.compareTo("H") == 0)
				{
					int temp = xBuf;
					xBuf = yBuf;
					yBuf = temp;
					
					grid.addEdge(grid.getPoint(xBuf, yBuf), grid.getPoint(xBuf + 1, yBuf));
				}
				else if (sBuf.compareTo("V") == 0)
					grid.addEdge(grid.getPoint(xBuf, yBuf), grid.getPoint(xBuf, yBuf + 1));
			}
			
			int[] result = new int[width + 1];
			for (int i = 1; i <= width; i++)
				result[i] = grid.findSquares(i);
			
			printAnswer(nProblem, result);
			
			nProblem++;
		}
	}
	
	private static void printAnswer(int serial, int[] result)
	{
		if (serial > 1)
		{
			System.out.println();
			System.out.println("**********************************");
			System.out.println();
		}
		
		System.out.println("Problem #" + serial);
		System.out.println();
		
		boolean noSquare = true;
		for (int i = 0; i < result.length; i++)
		{
			if (result[i] > 0)
			{
				System.out.println(result[i] + " square (s) of size " + i);
				noSquare = false;
			}
		}
		if (noSquare)
			System.out.println("No completed squares can be found.");
	}
}

class Grid
{
	private Point[][] points;
	
	public Grid(int width, int height)
	{
		points = new Point[height + 1][width + 1];
		for (int i = 0; i <= height; i++)
			for (int j = 0; j <= width; j++)
				points[i][j] = new Point(j, i);
	}
	
	public boolean inRange(int x, int y)
	{
		return (x >= 0 && x <= this.getWidth() && y >= 0 && y <= this.getHeight());
	}
	
	public Point getPoint(int x, int y)
	{
		if (inRange(x, y))
			return this.points[y][x];
		else 
			return null;
	}
	
	public int getHeight()
	{
		return this.points.length - 1;
	}
	
	public int getWidth()
	{
		return this.points[0].length - 1;
	}
	
	public Point getPoint(Point p, int dx, int dy)
	{
		if (inRange(p.getX() + dx, p.getY() + dy))
			return this.points[p.getY() + dy][p.getX() + dx];
		else
			return null;
	}
}
class MeshGrid extends Grid
{
	private Set<Edge> edgeSet;
	
	public MeshGrid(int width, int height)
	{
		super(width, height);
		this.edgeSet = new HashSet<Edge>();
	}
	
	public void addEdge(Point p1, Point p2)
	{
		if (p1.compareTo(p2) >= 0)
		{
			Point temp = p1;
			p1 = p2;
			p2 = temp;
		}
		
		if (p1.getY() == p2.getY() && p2.getX() - p1.getX() == 1) // Adding a horizontal edge.
		{
			this.edgeSet.add(new Edge(p1, p2));
			for (Point right = this.getPoint(p2, 1, 0); right != null; right = this.getPoint(right, 1, 0))
			{
				if (this.edgeSet.contains(new Edge(right, this.getPoint(right, -1, 0))))
					this.edgeSet.add(new Edge(p1, right));
				else break;
			}
			for (Point left = this.getPoint(p1, -1, 0); left != null; left = this.getPoint(left, -1, 0))
			{
				if (this.edgeSet.contains(new Edge(left, this.getPoint(left, 1, 0))))
					this.edgeSet.add(new Edge(left, p2));
				else break;
			}
		}
		else if (p1.getX() == p2.getX() && p2.getY() - p1.getY() == 1) // Adding a vertical edge.
		{
			this.edgeSet.add(new Edge(p1, p2));
			for (Point lower = this.getPoint(p2, 0, 1); lower != null; lower = this.getPoint(lower, 0, 1))
			{
				if (this.edgeSet.contains(new Edge(lower, this.getPoint(lower, 0, -1))))
					this.edgeSet.add(new Edge(p1, lower));
				else break;
			}
			for (Point upper = this.getPoint(p1, 0, -1); upper != null; upper = this.getPoint(upper, 0, -1))
			{
				if (this.edgeSet.contains(new Edge(upper, this.getPoint(upper, 0, 1))))
					this.edgeSet.add(new Edge(upper, p2));
				else break;
			}
		}
		else 
			System.out.println("[MeshGrid] Error : Adding oblique edges or non-unit edges.");
	}
	
	public int findSquares(int width)
	{
		int count = 0;
		
		for (int i = 0; i < this.getWidth() - width + 1; i++)
		{
			for (int j = 0; j < this.getHeight() - width + 1; j++)
			{
				Point leftTop = this.getPoint(i, j);
				Point rightTop = this.getPoint(leftTop, width, 0);
				Point leftBot = this.getPoint(leftTop, 0, width);
				Point rightBot = this.getPoint(leftTop, width, width); 
				if (this.edgeSet.contains(new Edge(leftTop, rightTop)) &&
					this.edgeSet.contains(new Edge(leftTop, leftBot)) &&
					this.edgeSet.contains(new Edge(leftBot, rightBot)) &&
					this.edgeSet.contains(new Edge(rightTop, rightBot)))
					count++;
			}
		}
		
		return count;
	}
	
	public String toString()
	{
		return this.edgeSet.toString();
	}
}
class Edge
{
	private Point start, end;
	
	public Edge(int x1, int y1, int x2, int y2)
	{
		this(new Point(x1, y1), new Point(x2, y2));
	}
	
	public Edge(Point start, Point end)
	{
		if (start.compareTo(end) <= 0)
		{
			this.start = start;
			this.end = end;
		}
		else 
		{
			this.start = end;
			this.end = start;
		}
	}
	
	public Point getStartPoint()
	{
		return this.start;
	}
	
	public Point getEndPoint()
	{
		return this.end;
	}
	
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		
		sb.append("[").append(this.start.toString()).append("--").append(this.end.toString()).append("]");
		
		return sb.toString();
	}
	
	public boolean equals(Object o)
	{
		if (!(o instanceof Edge))
			return false;
		
		Edge e = (Edge) o;
		return this.getStartPoint().compareTo(e.getStartPoint()) == 0 &&
			   this.getEndPoint().compareTo(e.getEndPoint()) == 0;
	}
	
	public int hashCode()
	{
		int result = 7;
		result = 23 * result + this.getStartPoint().getX();
		result = 23 * result + this.getStartPoint().getY();
		result = 23 * result + this.getEndPoint().getX();
		result = 23 * result + this.getEndPoint().getY();
		
		return result;
	}
}
class Point implements Comparable<Point>
{
	private int x, y;
	
	public Point(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
	
	public int getX()
	{
		return this.x;
	}
	
	public int getY()
	{
		return this.y;
	}
	
	public int compareTo(Point p)
	{
		return (this.x - p.x != 0) ? (this.x - p.x) : (this.y - p.y);
	}
	
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		
		sb.append("(").append(this.x).append(",").append(this.y).append(")");
		
		return sb.toString();
	}
}