## 10855 - Rotated square

Moderator: Board moderators

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

### 10855 - Rotated square

Hi all,
I'm getting WA for this easy problem. Please give me some I/O. By the way i'm giving the code to rotate the small square. Is it ok ???? Thankx in advance.

Code: Select all

``````void rotate_grid()
{
int i,j;
int sro1r,sro1c,sro2r,sro2c,sro3r,sro3c;
int rot1r,rot1c,rot2r,rot2c,rot3r,rot3c,rot4r,rot4c;

sro1r=0;		// 90 degree
sro1c=n-1;

sro2r=n-1;		// 180 degree
sro2c=0;

sro3r=0;		// 270 degree
sro3c=-(n-1);

// Given Second Square is already at rot[0][]][]
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
rot1r=i;	// 0 degree
rot1c=j;
rot2r=i+sro1r+j;	// 90 degree
rot2c=j+sro1c-j;

rot3r=rot2r+sro2r-j;	// 180 degree
rot3c=rot2c+sro2c-j;

rot4r=rot3r+sro3r-j;	// 270 degree
rot4c=rot3c+sro3c+j;

rot[1][rot2r][rot2c]=rot[0][rot1r][rot1c];
rot[2][rot3r][rot3c]=rot[0][rot1r][rot1c];
rot[3][rot4r][rot4c]=rot[0][rot1r][rot1c];
}
sro1r--;
sro1c--;

sro2r--;
sro2c++;

sro3r++;
sro3c++;
}
/*for(i=0;i<n;i++)
{
for(j=0;j<4;j++)
pf(" %s",rot[j][i]);
puts("");
}
puts("");*/

}
``````

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi Chok

I have found a mistake in your code
just add this line after calling the rotated_grid() function.

Code: Select all

``````for (i = 0; i < n; i++)
rot[1][i][n] = NULL, rot[2][i][n] = NULL, rot[3][i][n]= NULL;
``````
Thanks
MAP

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi Prince,
Thanks for ur help. But i'm still not get ACC. I think my checking is not ok. Here is my full code. Please verify it. Thanks in advance.

Code: Select all

``````Cut after Acc...
``````
Last edited by Chok on Wed Jul 27, 2005 5:21 pm, edited 1 time in total.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi

just increase ur max value and get your AC.

Thanks
MAP

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi Prince,
Thank you very much. Got ACC. I missed those think. Again thanx. Bye and Good luck.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I changed my solution to one that only computes hash values, and it turns out that I can get AC in 0.006s

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Interesting, what's your hash function? I wonder how it works.....

There's no upper bound on N or n correct? I tried brute force and got AC with 9.2 sec by luck. I guess that means N can be big?

Pregunt
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:

### n<=100

N<=100

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10855 - Rotated squares

I just got AC in 0.045 using the straightforward brute force method of making up to (N - n + 1) * (N - n + 1) * n * n comparisons or O(N * N * n * n). I stopped comparing the small square when there was a mismatch.

I improved my time to 0.009 using a hash.
First iterate fully through one dimension and use a rolling hash to shrink the small square to 1 by n and the large square to (N - n + 1) by N. Then iterate through the other dimension and you can reduce the small square to 1 by 1 and the large square to (N - n + 1) by (N - n + 1). Now you only have to make (N - n + 1) * (N - n + 1) comparisons and the whole code runs in O(N * N) which is optimal.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10855 - Rotated squares

Here's some input / output I found useful during testing / debugging.

Input:

Code: Select all

``````9 2
ABBAABABA
ABBBABABA
BAAAABBAB
BABBBABAB
ABBBBABAB
BBBABABAB
ABABABBBA
ABABABBBA
BBABABBAB
AB
BB
7 2
ABCCBAB
BCCBABA
BACCCAB
BABABCC
CABABAB
ABCBABA
BACCABA
AB
BC
0 0
``````
AC Output:

Code: Select all

``````4 3 3 3
2 1 1 0
``````
Check input and AC output for over 7,500 problems on uDebug!

yammacode
New poster
Posts: 1
Joined: Sun Apr 05, 2015 9:34 pm

### Re: 10855 - Rotated square

Hi. I got WA. Here's my code.

Code: Select all

``````#include <iostream>

using namespace std;

int N, n;
char big[100][100];
char small[100][100];

int main(void) {

std::cin>>N>>n;
while(true) {
if(N == 0 || n == 0)
break;

int result[4] = {0,0,0,0};

for(int i=0; i<N; i++)
for(int k=0; k<N; k++)
std::cin>>big[i][k];

for(int i=0; i<n; i++)
for(int k=0; k<n; k++)
std::cin>>small[i][k];

for(int i=0; i<=N-n; i++) {
for(int k=0; k<=N-n; k++) {

int n_j = 0, n_l = 0;

for(int j=i; j<i+n; j++) {
n_l = 0;
for(int l=k; l<k+n; l++) {
if(big[j][l] != small[n_j][n_l++]) {
goto fail;
}
}
n_j++;
}
result[0]++;
fail: ;

n_j = 0;

for(int j=i; j<i+n; j++) {
n_l = n-1;
for(int l=k; l<k+n; l++) {
if(big[j][l] != small[n_j][n_l--]) {
goto fail2;
}
}
n_j++;
}
result[1]++;
fail2: ;

n_j = n-1;

for(int j=i; j<i+n; j++) {
n_l = n-1;
for(int l=k; l<k+n; l++) {
if(big[j][l] != small[n_j][n_l--]) {
goto fail3;
}
}
n_j--;
}
result[2]++;
fail3: ;

n_j = n-1;
for(int j=i; j<i+n; j++) {
n_l = 0;
for(int l=k; l<k+n; l++) {
if(big[j][l] != small[n_j][n_l++]) {
goto fail4;
}
}
n_j--;
}
result[3]++;
fail4: ;

}
}

std::cout<<result[0]<<" "<<result[1]<<" "<<result[2]<<" "<<result[3]<<std::endl;

std::cin>>N>>n;
}

return 0;
}``````

yoyoshubham
New poster
Posts: 1
Joined: Fri Jun 24, 2016 10:33 am

### Re: 10855 - Rotated square

Hi all! I am getting WA on the judge, but my code is giving correct output for sample test cases provided on https://www.udebug.com/UVa/10855 . Can anyone help me find out the mistake in my code.

Code: Select all

``````Deleted after getting AC :D
``````

Sebassmaster
New poster
Posts: 2
Joined: Fri Aug 19, 2016 1:51 am

### Re: 10855 - Rotated square

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;
}

``````