KNIGHT ATTACKS - SOLUTION
Area: two-dimensional arrays - matrices
#include<iostream>
#include<string>
using namespace std;
int main() {
#include<string>
using namespace std;
int main() {
// Entering the coordinates of the knight's position (row and column)
int m, n;
cin >> m >> n;
// Initializing the board as a matrix of strings
string tabla[9][9];
// Filling the board from row 8 to 1
for (int i = 8; i >= 1; i--) {
// Printing the contents of the board
for (int i = 8; i >= 1; i--) {
return0;
}
int m, n;
cin >> m >> n;
// Initializing the board as a matrix of strings
string tabla[9][9];
// Filling the board from row 8 to 1
for (int i = 8; i >= 1; i--) {
for (int j = 1; j <= 8; j++) {
}if (i == m && j == n) { // If the current position is the knight
}int v = 0; // Helper variable for shifting columns
for (int r = i + 2; r >= i - 2; r--) {
} else {for (int r = i + 2; r >= i - 2; r--) {
// Placing '0' at the knight's position
tabla[i][j] = " 0";
if (r > i) v++; // Shifting the column to the right
else if (r < i - 1) v--; // Shifting the column to the left
else if (r == i) {
// Ignoring positions outside the board
if (r < 1 || r > 8) continue;
// Calculating the columns of the right and left attacked fields
int k1 = n + v; // Right
int k2 = n - v; // Left
// Generating field labels (e.g. 'c4')
char kol1 = 'a' + k1 - 1;
char kol2 = 'a' + k2 - 1;
char red = '0' + r;
string s1 = ""; // Attacked field on the right
s1 += kol1;
s1 += red;
string s2 = ""; // Attacked field on the left
s2 += kol2;
s2 += red;
// Placing the attacked fields on the board
if (k1 <= 8) tabla[r][k1] = s1;
if (k2 >= 1) tabla[r][k2] = s2;
}tabla[i][j] = " 0";
if (r > i) v++; // Shifting the column to the right
else if (r < i - 1) v--; // Shifting the column to the left
else if (r == i) {
// In the same row as the knight, '*' is placed
tabla[i][j] = " *";
continue;
}tabla[i][j] = " *";
continue;
// Ignoring positions outside the board
if (r < 1 || r > 8) continue;
// Calculating the columns of the right and left attacked fields
int k1 = n + v; // Right
int k2 = n - v; // Left
// Generating field labels (e.g. 'c4')
char kol1 = 'a' + k1 - 1;
char kol2 = 'a' + k2 - 1;
char red = '0' + r;
string s1 = ""; // Attacked field on the right
s1 += kol1;
s1 += red;
string s2 = ""; // Attacked field on the left
s2 += kol2;
s2 += red;
// Placing the attacked fields on the board
if (k1 <= 8) tabla[r][k1] = s1;
if (k2 >= 1) tabla[r][k2] = s2;
if (tabla[i][j].length() == 0) {
}// Filling the other fields with '*'
tabla[i][j] = " *";
}tabla[i][j] = " *";
// Printing the contents of the board
for (int i = 8; i >= 1; i--) {
for (int j = 1; j <= 8; j++) {
cout << endl;
}cout << tabla[i][j] << " ";
}cout << endl;
return0;
Key parts of the code and explanation
Initializing the board:
string tabla[9][9];
A two-dimensional 9x9 array of strings is created, which will represent the chessboard. Although the board is 8x8, a 9x9 matrix is used for easier indexing (indices go from 1 to 8, which matches chess notation).The loop that fills the board:
for(int i=8; i>=1; i--)
{
This loop goes through all the positions on the chessboard, starting from the bottom row (i=8) toward the top (i=1), and from the left to the right column (j=1 to j=8).{
for(int j=1; j<=8; j++)
{
{
Finding the knight's position:
if(i==m && j==n)
When the knight's position (m, n) is reached, the program starts marking the fields the knight attacks.
Marking the fields the knight attacks:
for(int r=i+2; r>=i-2; r--)
This loop iterates through all the rows the knight can attack (two rows above and two below the knight's position). Changing the variable v is used to mark the column shift depending on the current row.- k1 and k2 are the columns the knight attacks.
- kol1 and kol2 are the labels of those columns (a-h).
- red is the row the knight attacks (1-8).
- s1 and s2 are the codes of the fields the knight attacks.
Marking the knight's position:
tabla[i][j]=" 0";
At the position where the knight is, " 0" is placed to mark that it is the knight's position.Filling the other fields:
if((tabla[i][j]).length()==0)
{
All the other fields that are not attacked or don't hold the knight are filled with asterisks (*).{
tabla[i][j]=" *";
}Printing the board:
for(int i=8; i>=1; i--)
{
At the end the board is printed so that each line is one row of the chessboard.{
for(int j=1; j<=8; j++)
{
cout << endl;
}{
cout << tabla[i][j] << " ";
}cout << endl;
ResultAs a result, the output is a chessboard with the labels of the fields the knight attacks, the knight's position marked with " 0", and the other fields filled with asterisks.
This program nicely shows the basic principles of working with two-dimensional arrays, string manipulation and basic algorithm concepts in C++.
Analysis of how optimal the code is
- Extra iterations:
- The current code uses a loop that goes through 25 possible positions around the knight, including those the knight cannot reach. The knight can attack only eight specific positions (if they are inside the board), so checking all these 25 positions is unnecessary.
- Redundant placing of asterisks:
- The code first goes through all the positions and places an asterisk (*) on each one that is not attacked. This process could be optimized so that the asterisks are placed during the first pass through the matrix, and not after checking all the fields.
Optimized code
#include<iostream>
#include<string>
using namespace std;
int main() {
#include<string>
using namespace std;
int main() {
// Entering the knight's position (row and column)
int m, n;
cin >> m >> n;
// Matrix representing the chessboard
string tabla[9][9];
// Defining all possible knight moves
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};
// Filling the board with starting values
for (int i = 8; i >= 1; --i) {
// Checking the fields the knight can attack
for (int k = 0; k < 8; ++k) {
// Printing the chessboard
for (int i = 8; i >= 1; --i) {
return0;
}
int m, n;
cin >> m >> n;
// Matrix representing the chessboard
string tabla[9][9];
// Defining all possible knight moves
int dx[] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[] = {1, -1, 2, -2, 1, -1, 2, -2};
// Filling the board with starting values
for (int i = 8; i >= 1; --i) {
for (int j = 1; j <= 8; ++j) {
}if (i == m && j == n) {
}// The knight's current position marked with "0"
tabla[i][j] = " 0";
} else {tabla[i][j] = " 0";
// We assume all other fields are not attacked
tabla[i][j] = " *";
}tabla[i][j] = " *";
// Checking the fields the knight can attack
for (int k = 0; k < 8; ++k) {
// New coordinates of the knight's move
int ni = m + dx[k];
int nj = n + dy[k];
if (ni >= 1 && ni <= 8 && nj >= 1 && nj <= 8) {
}int ni = m + dx[k];
int nj = n + dy[k];
if (ni >= 1 && ni <= 8 && nj >= 1 && nj <= 8) {
// Converting coordinates to chess notation (e.g. c4)
char kol = 'a' + nj - 1;
char red = '0' + ni;
tabla[ni][nj] = string(1, kol) + red;
}char kol = 'a' + nj - 1;
char red = '0' + ni;
tabla[ni][nj] = string(1, kol) + red;
// Printing the chessboard
for (int i = 8; i >= 1; --i) {
for (int j = 1; j <= 8; ++j) {
cout << endl;
}cout << tabla[i][j] << " ";
}cout << endl;
return0;
Improvements in the optimized code
- Clarity and simplicity: All possible knight moves are clearly defined in two arrays (dx and dy). These arrays make it simple to iterate through all the positions the knight can attack.
- Efficiency: The code now uses only one loop to iterate through all the attacked positions, instead of unnecessary iterations through positions the knight cannot attack.
- Correctness: This code also checks whether the attacked fields are inside the board, which avoids placing codes on fields that don't exist.
Solution-Jumper Attack
#include <iostream>#include<string>
using namespacestd;
int main()
{
int m,n;
cin>>m>>n;
string tabla[9][9];
for(int i=8; i>=1; i--)
{
for(int j=1; j<=8; j++)
{
if(i==m && j==n)
{
int v=0;
for(int r=i+2; r>=i-2; r--)
{
tabla[ i ][ j ]=" 0"; //Prints 0 at the place where the position with m and n is set
if(r>i)
v++; //Moving a column for a field that is attacking a jumper
else if(r<i-1)
v--; //Moving a column for a field that is attacking a jumper
else if(r==i) //In the same row where the jumper has no attack field, there is an asterisk
{
tabla[i][j]=" *";
continue;
}
if(r<1||r>8)continue; //out of range
int k1=n+v; //column of the attacked field on the right
int k2=n-v; //column of the attacked field on the left
char kol1='a'+k1-1; //the column label of the attacked field on the right (a-h)
char kol2='a'+k2-1; //mark of the column of the attacked field on the left (a-h)
char red='0'+r; //right-clicked code marker (1-8)
string s1="";
s1+=kol1;
s1+=red;
string s2="";
s2+=kol2;
s2+=red;
if(k1<=8)
tabla[r][k1]=s1; //the number of the attacked field on the right
if(k2>=1)
tabla[r][k2]=s2; //the number of the attacked field left
}
}
else
{
if((tabla[i][j]).length()==0)
{
tabla[i][j]=" *"; //Other fields fill with an asterisk
}
}
}
}
/* Printing*/
for(int i=8; i>=1; i--)
{
for(int j=1; j<=8; j++)
{
cout<<tabla[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
