Chef And Squares CHSQR

PROBLEM:-CHSQR SUBMIT IN PRACTICE :-submit

DIFFICULTY:- EASY

PREREQUISITE:- Knowledge of Loops .

PROBLEM:- Chef has to fill a K x K square grid of integers in a certain way. Let us say that such a grid is valid if:

• Each cell contains an integer from 1 and K (inclusive).
• No integer appears twice in the same row or the same column.

Let F(K) be maximum possible distance between the center of the square and the closest cell that contains 1, among all possible squares with the side length K.

Here, we use the following notions:

• The distance between cell (x, y) and (i, j) is equal to |x-i|+|y-j|.
• The center of a K x K square is cell ((K+1)/2, (K+1)/2) for odd K.

For More about the Problem and constraints , read the complete Problem HERE.

INPUT FORMAT:-

The first line of input contains a single integer T denoting the number of test cases.
Each test case consists of a single line containing a single odd integer K.

OUTPUT FORMAT:-

For each test case, print K lines each consisting of K space separated integers giving some square grid where the distance from the center of the grid to the nearest 1 is exactly F(K). If there’s more than 1 possible answer output any of them.

EXPLANATION :- Read the 4th line of the problem statement very carefully, saying that F(K) be maximum possible distance between the center of the square and the closest cell that contains 1. Now as we know each of K cells of a row contains a unique number means each row should have all numbers fron 1 to k. And similar rule applies for the column. Thus each column should have one 1. So, the middle column should also have one 1 and we have to keep this 1 as far as possible from the center of square grid so either we can place it on topmost row or on the bottom most row. If we place it on top most row now no another 1 can come to this row.Now in order to keep 1 in second row we will keep it either the left of the previous 1 or right the previous 1 so as to keep the distance from the center maximum. So, for K=5 our k*k matrix will look like.

You can see how I, have arranged 1’s by shifting them one position left each time. After the middle row on shifting left by applying loop and taking modulus you will automatically reach rightmost position (see 4th row) and then again shift one position left.

So, Now for k=7 our k*k matrix will look like.

CODE IN C++:-

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int t,n,count1,count2,x,j;
cin>>t;
while(t--)
{
cin>>n;
if(n!=1)
{
count1=n;
count2=n;
x=n-n/2+1; // initializing x from left corner value
for(int i=0;i<count1;i++) // for changing rows
{
for(j=0;j<count2;j++) //for changing columns
{
cout<<x<<" ";
if(j!=count2-1)
{
x++;
if(x>n)
x=x%n; //Take modulus every number changing calculation will be done by this automatically.
}
else //this is because see the last element of row after printing last element you have to change row and after changing row
{ //You have to increase your printing value by 2 from next row that is why we add 2 to x;
x=x+2;
if(x>n)
x=x%n; //Take modulus every number changing calculation will be done by this automatically.
}
}
cout<<endl;
}
}
else
{
cout<<"1"<<endl; //Handle case of 1 separately.
}
}
}
#Happy_Coding #Codebrace #A_U_V
If you find something wrong or have any question about the solution then comment down below, you can also contact us using  contact form