Hi All,
All testcases are passing (both from sample and uDebug), but I'm still getting WA. Please heeelp
!!
Code: Select all
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cmath>
std::ostream& operator<<(std::ostream& out, std::vector<std::string> const& square)
{
for(auto const& row : square)
out << row << std::endl;
return out;
}
//#define DEBUG
namespace debug
{
struct X {
template<typename T>
X& operator << (const T& x)
{
#ifdef DEBUG
std::cout << x;
#endif
return *this;
}
} cout;
} // namespace mystd
using SquareT = std::vector<std::string>;
/**
* @brief Rotates a certain layer of a square, in place.
* It doesn't touch any field that's outside that particular layer.
*
* @param layer 0-Based layer to rotate
* @param square square in which the layer will be rotated
*/
void rotate_layer_90(int const layer, SquareT& square)
{
int const col_min = layer;
int const col_max = square.size() - layer - 1;
int const row_min = layer;
int const row_max = col_max;//-> Making use that this is a square
int const sub_square_size = row_max - row_min + 1;
//Base case 1X1: The result is the same number, nothing to do
if(sub_square_size == 1) return;
//Base case 2X2: solved by swapping its elements in the correct order
if(sub_square_size == 2){
std::swap(square[row_min][col_min], square[row_min][col_max]);
std::swap(square[row_min][col_min], square[row_max][col_min]);
std::swap(square[row_max][col_min], square[row_max][col_max]);
return;
}
char const temp_bottom_right_char = square[row_max][col_max];
char const temp_upper_left_char = square[row_min][col_min];
char const temp_upper_right_char = square[row_min][col_max];
//Shifting Left column up
for (int i = row_min; i < row_max; ++i) {
square[i][col_min] = square[i+1][col_min];
}
//Shifting upper row right
for (int i = col_max; i > col_min; --i) {
square[row_min][i] = square[row_min][i-1];
}
//Shifting right column down
for (int i = row_max; i > row_min; --i) {
square[i][col_max] = square[i-1][col_max];
}
//Shifting bottom row left
for (int i = col_min; i < col_max; ++i) {
square[row_max][i] = square[row_max][i+1];
}
square[row_min][col_min+1] = temp_upper_left_char;
square[row_max][col_max-1] = temp_bottom_right_char;
square[row_min+1][col_max] = temp_upper_right_char;
}
/**
* @brief Rotates an entire square 90 degrees
*
* @param square square to rotate (immutable)
*
* @return a new square which is the 90 degrees rotation of the input square
*/
SquareT rotate_square_90(SquareT const& square)
{
SquareT out(square);
auto n = square.size();
int const n_layers = std::floor((n+1)/2);
//Cicle through layers
for (int i = 0; i < n_layers; ++i) {
rotate_layer_90(i, out);
}
return out;
}
/**
* @brief Checks if a small square is equal to a same size (possible)subset of a big square
*
* @param small small square
* @param big big square
* @param min_row smallest row to check in the big square
* @param min_col smallest column to check in the big square
* @param n_cols small square size
* @param n_rows small square size
*
* @return
*/
bool small_appears_in_big(SquareT const& small, SquareT const& big, int const min_row, int const min_col, int const n_cols, int const n_rows)
{
for (int i = 0; i < n_rows; ++i) {
for (int j = 0; j < n_cols; ++j) {
if(small[i][j] != big[i+min_row][j+min_col])
return false;
}
}
return true;
}
/**
* @brief Counts the apparance of a specific small square in a big one
*
* @param small
* @param big
*
* @return number of appareances of the small square in the big one
*/
int count_appearances(SquareT const& small, SquareT const& big)
{
int const n_checkings = big.size() - small.size() + 1;
int const n_rows = small.size();
int const n_cols = small.size();
int count = 0;
for (int i = 0; i < n_checkings; ++i) {
for (int j = 0; j < n_checkings; ++j) {
int const min_row = i;
int const min_col = j;
if(small_appears_in_big(small, big, min_row, min_col, n_rows, n_cols))
count++;
}
}
return count;
}
/**
* @brief Reports the count of the appareances of the small square in the big square
*
* @param big_square
* @param small_square
*
* @return A string containing the count of appareances of the small square in the big square in: 0deg, 90deg, 180deg and 270deg
*/
std::string analyze_squares(SquareT const& big_square, SquareT const& small_square)
{
std::stringstream out;
int deg_0_appearances_count = count_appearances(small_square, big_square);
auto deg_90 = rotate_square_90(small_square);
int deg_90_appearances_count = count_appearances(deg_90, big_square);
auto deg_180 = rotate_square_90(deg_90);
int deg_180_appearances_count = count_appearances(deg_180, big_square);
auto deg_270 = rotate_square_90(deg_180);
int deg_270_appearances_count = count_appearances(deg_270, big_square);
out << std::to_string(deg_0_appearances_count) << " "
<< std::to_string(deg_90_appearances_count) << " "
<< std::to_string(deg_180_appearances_count) << " "
<< std::to_string(deg_270_appearances_count);
return out.str();
}
int main(int argc, char *argv[])
{
std::string line;
while(std::getline(std::cin, line))
{
std::stringstream ss_line(line);
int big_n, small_n;
ss_line >> big_n >> small_n;
if(big_n == 0 and small_n == 0)
break;
SquareT big_square, small_square;
for (int i = 0; i < big_n; ++i) {
std::string row;
std::getline(std::cin, row);
big_square.push_back(row);
}
for (int i = 0; i < small_n; ++i) {
std::string row;
std::getline(std::cin, row);
small_square.push_back(row);
}
std::cout << analyze_squares(big_square, small_square) << std::endl;
}
return 0;
}
