UVa 201

Squares.cpp

#include <stdio.h>
#include <vector>
#include <map>
#include <iostream>
#include <string>

using namespace std;

int boardBoundary;
vector<int> pathDirectList;
map<int, map<int, bool>> connectionGraphic;

void initializeBoard()
{
	connectionGraphic.clear();
	pathDirectList = vector<int>{ 1, boardBoundary, -1, -boardBoundary };
}

void linkHorizonLineAtBoard(int row, int col)
{
	auto startPointIndex = (row - 1) * boardBoundary + col - 1;
	auto endPointIndex = (row - 1) * boardBoundary + col;
	connectionGraphic[startPointIndex][endPointIndex] = true;
	connectionGraphic[endPointIndex][startPointIndex] = true;
}

void linkVerticalLineAtBoard(int col, int row)
{
	auto startPointIndex = (row - 1) * boardBoundary + col - 1;
	auto endPointIndex = row * boardBoundary + col - 1;
	connectionGraphic[startPointIndex][endPointIndex] = true;
	connectionGraphic[endPointIndex][startPointIndex] = true;
}

bool isTwoIndexConnected(int destination, int targetIndex)
{
	if (connectionGraphic.count(destination))
	{
		auto destinationGraphic = connectionGraphic[destination];
		return destinationGraphic.count(targetIndex) > 0;
	}
	return false;
}

int traverseGraphicFrom(int beginIndex, int edgeLength)
{
	auto edgeIndex = 0;
	for (edgeIndex = 0; edgeIndex < pathDirectList.size(); edgeIndex++)
	{
		for (auto i = 0; i < edgeLength; i++)
		{
			if (!isTwoIndexConnected(beginIndex, beginIndex + pathDirectList[edgeIndex]))
			{
				return edgeIndex;
			}
			beginIndex += pathDirectList[edgeIndex];
		}
	}

	return edgeIndex;
}

void countSquare(int startIndex, int maxEdgeLength, vector<int> &result)
{
	for (auto edgeLength = 1; edgeLength < maxEdgeLength; edgeLength++)
	{
		auto stopedEdgeIndex = traverseGraphicFrom(startIndex, edgeLength);
		if (stopedEdgeIndex == 0)
		{
			break;
		}
		else if (stopedEdgeIndex == pathDirectList.size())
		{
			result[edgeLength - 1]++;
		}
	}
}

vector<int> solve()
{
	vector<int> result(boardBoundary, 0);
	auto boundaryIndex = 0, endIndex = boardBoundary * (boardBoundary - 1);
	for (auto startIndex = 0; startIndex < endIndex; startIndex++)
	{
		if (startIndex%boardBoundary == 0)
		{
			boundaryIndex = ((startIndex / boardBoundary) + 1) * boardBoundary;
		}
		countSquare(startIndex, boundaryIndex - startIndex, result);
	}
	return result;
}

void outputResults(int problemQuantity, vector<int> &resultSquares)
{
	if (problemQuantity > 1)
	{
		printf("\n**********************************\n\n");
	}

	bool isSquareExist = false;
	printf("Problem #%d\n\n", problemQuantity);
	for (auto squareSize = 0; squareSize < resultSquares.size(); squareSize++)
	{
		auto squareQuantity = resultSquares[squareSize];
		if (squareQuantity > 0)
		{
			printf("%d square (s) of size %d\n", resultSquares[squareSize], squareSize + 1);
			isSquareExist = true;
		}
	}

	if (!isSquareExist)
	{
		puts("No completed squares can be found.");
	}
}

int main()
{
	auto typeString = string{};
	auto m = 0, row = 0, col = 0, problemQuantity = 1;
	while (~scanf("%d%d", &boardBoundary, &m))
	{
		initializeBoard();
		for (auto i = 0; i < m; i++)
		{
			cin >> typeString >> row >> col;
			if (typeString == "H")
			{
				linkHorizonLineAtBoard(row, col);
			}
			else
			{
				linkVerticalLineAtBoard(row, col);
			}
		}

		auto resultSquares = solve();
		outputResults(problemQuantity++, resultSquares);
	}
	return 0;
}