26. SNAIL – TASK SOLUTION
Task text:
/*
Nemanja is 6 years old and has started learning to read and write. His uncle gave him a workbook for learning letters which contains the exercise "Snail".
In this exercise there is a table of size n x m into which a sentence must be written in the following way:
you start from the top-left corner of the table and write the letters towards the right edge of the table as far as you can. When you reach the edge, you continue
writing downwards to the edge, then to the left to the edge, then upwards while there is room, then again to the right, and so on until the whole table is filled (picture).
Only letters are written into the table; spaces, punctuation marks and similar characters are ignored.
Since Nemanja is too young for this exercise, his uncle filled in the table.
Now Nemanja wants to know whether the sentence used to fill the table contains the name of his favourite superhero.
Since Nemanja does not know all the letters yet, help him find out.
Input
The first line of standard input contains two integers n and m (2 ≤ n, m ≤ 50),
which are the number of rows and the number of columns of the table.
Each of the next n lines contains m characters (lowercase letters of the English alphabet),
which together make up the filled table.
The next line contains a string of characters (of length up to 30) which is the name of
Nemanja's favourite superhero (also lowercase letters of the English alphabet, without spaces or punctuation marks).
Output
In the only line of standard output, print one integer which is the
position in the sentence where the name of the superhero starts.
If the name does not exist, print -1.
If the name appears more than once, print the starting position of the first occurrence.
*/
Example 1
Input
4 5
mnogo
jdrmv
aaneo
psmil
spajdrmen
Output
11
Explanation
When the table is unrolled, we get the string mnogovolimspajdrmena
(Serbian for "I love Spider-Man very much"),
so the word spajdrmen appears starting from position 11.
Example 2
Input
5 5
dalis
rnuui
ccudt
oivoi
adelg
crnaudovica
Output
-1
Explanation
Although the sentence is about the Black Widow (Serbian: crna udovica), the string crnaudovica
does not appear, because in the sentence her name is in a different grammatical case (the accusative).
Solution
First the whole text is read as a matrix of cells, where each cell holds one character.
The matrix here is actually a vector of strings, where each string is one row of the table.
Then the word we are looking for is read. The search is linear and goes through one string that contains the whole text,
but this string is filled in the direction shown in the picture. The direction is changed in a do-while loop,
and the inner for loop goes through the current row or column in the direction that corresponds to the current direction of movement.
The direction changes after the inner loop has finished, and it is analysed with a switch statement.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
int m, n;
cin >> n >> m; // We read the dimensions of the matrix: n rows and m columns
string superhero;
vector<string> table(n);
// Reads the text row by row, where table[i] is a row of text
for (int i = 0; i < n; i++)
cin >> table[i];
cin >> superhero; // Reads the word we are looking for in the spiral
// Initializing the variables for moving through the matrix
int currentRow = 0; // Current row for moving horizontally
int currentCol = m - 1; // Current column for moving vertically
int startR = 0; // Starting row of the current spiral
int endR = n - 1; // Ending row of the current spiral
int startC = 0; // Starting column of the current spiral
int endC = m - 1; // Ending column of the current spiral
int direction = 1; // Current direction: 1-right, 2-down, 3-left, 4-up
string text = ""; // String of characters in the shape of a snail
int pos = -1; // Position where the superhero's name starts
// Main loop for moving through the matrix in the shape of a snail
do {
switch (direction) // We analyse the current direction
{
case 1: // Right
for (int i = startC; i <= endC; i++)
text += table[currentRow][i]; // We add the characters of the row
startR++; // Move the starting row down
currentRow = endR; // Preparation for the next vertical direction
break;
case 2: // Down
for (int i = startR; i <= endR; i++)
text += table[i][currentCol]; // We add the characters of the column
endC--; // Move the ending column to the left
currentCol = startC; // Preparation for the next horizontal direction
break;
case 3: // Left
for (int i = endC; i >= startC; i--)
text += table[currentRow][i]; // We add the characters of the row backwards
endR--; // Move the ending row up
currentRow = startR; // Preparation for the next vertical direction
break;
case 4: // Up
for (int i = endR; i >= startR; i--)
text += table[i][currentCol]; // We add the characters of the column backwards
startC++; // Move the starting column to the right
currentCol = endC; // Preparation for the next horizontal direction
break;
}
// Changing the direction clockwise
direction++;
direction %= 4; // We keep the direction in the range 1-4
if (direction == 0) direction = 4;
} while (endC >= startC && endR >= startR); // While the spiral is not finished
// Looks for the position of the superhero in the resulting string
pos = text.find(superhero);
if (pos != -1)
cout << pos + 1 << endl; // We print the 1-based position
else
cout << pos << endl; // If it does not exist, we print -1
return 0;
}
This task requires us to simulate the movement of a snail through a matrix, i.e. an n × m table, in order to create a string without punctuation marks and spaces.
The task is solved by following the movement of the snail in four directions: right, down, left and up, using variables that control the start and the end of the rows and columns.
Finally, we search the resulting string to find the position of Nemanja's favourite superhero. The program uses the function find()
to search for a substring, and the result is printed according to the given rules.
Comment and analysis of the solution
The solution is correct and working, because it correctly simulates the spiral (snail) through the matrix and correctly finds the position of the given name.
The structure of the code is clear and uses understandable logic for changing direction with a switch statement and a do-while loop.
The efficiency of the solution is satisfactory for the limits of the task (up to 50×50 elements), because the complexity is O(n·m) for building the string and O(k) for the substring search.
Possible improvements include:
- More precise variable names (e.g.
rowStart,columnEnd) for better readability. - Removing small inconsistencies in the comments (e.g. the descriptions of moving rows and columns).
- Adding a function for generating the spiral string for more modular code.
- A possible optimization: searching while the spiral string is being built, to avoid storing the whole string at once.
Despite these small improvements, the implementation is quite good and gives the correct result, so it can be considered a correct and efficient enough solution of the task.
Solution 2 - Snail (spiral) and searching for the superhero's name
Solving this task requires reconstructing the sentence from the given n×m matrix by moving in the shape of a snail (in a spiral),
and then checking whether the superhero's name exists in that sentence. The solving procedure includes the following steps:
- Reconstruct the sentence from the matrix in the "snail" shape.
- Remove all irrelevant characters and spaces (if needed).
- Find the position of the first occurrence of the superhero's name in the sentence (if it exists).
- Print the result.
Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function that returns the characters of the matrix in spiral order
vector<char> spiral(vector<vector<char>>& matrix, int rows, int cols) {
vector<char> result;
// Initializing the bounds of the matrix
int top = 0, bottom = rows - 1;
int left = 0, right = cols - 1;
// We continue while the bounds do not overlap
while (top <= bottom && left <= right) {
// We move from left to right along the top row
for (int i = left; i <= right; i++) {
result.push_back(matrix[top][i]);
}
top++; // Moves the top bound down
// We move from top to bottom along the right column
for (int i = top; i <= bottom; i++) {
result.push_back(matrix[i][right]);
}
right--; // Moves the right bound to the left
// We move from right to left along the bottom row, if there are rows left
if (top <= bottom) {
for (int i = right; i >= left; i--) {
result.push_back(matrix[bottom][i]);
}
bottom--; // We move the bottom bound up
}
// We move from bottom to top along the left column, if there are columns left
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.push_back(matrix[i][left]);
}
left++; // We move the left bound to the right
}
}
return result; // We return the reconstructed sentence
}
int main() {
int rows, cols;
cin >> rows >> cols; // We read the dimensions of the matrix
// We read the matrix of characters row by row
vector<vector<char>> matrix(rows, vector<char>(cols));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cin >> matrix[i][j]; // We read each character
}
}
string superhero;
cin >> superhero; // We read the name of the superhero
// We create the string of characters in spiral order using the function spiral
vector<char> sentence = spiral(matrix, rows, cols);
string created_sentence(sentence.begin(), sentence.end());
// We look for the position of the superhero's name in the reconstructed sentence
size_t found = created_sentence.find(superhero);
if (found != string::npos) {
cout << found + 1 << endl; // We print the 1-based position
} else {
cout << -1 << endl; // If the word does not exist, we print -1
}
return 0;
}
Comment on the solution:
This version is efficient because it uses the standard algorithm for traversing a matrix "in a spiral", known as the "snail".
The function spiral handles the bounds of the matrix elegantly and adds the characters to the result in the order they are visited.
Every step is commented in detail so that the logic of moving the bounds is clear.
The search for the superhero's name is done directly on the reconstructed sentence using the standard function find.
The program correctly returns the position of the first occurrence, or -1 if the word is not present.
Advantages of this approach:
- Readable and modular code thanks to the function
spiral. - Clearly defined bounds and directions of movement through the matrix.
- Efficiency that is enough for the standard matrix sizes (up to 50×50).
Possible improvements:
- Automatically filtering unnecessary characters before the search (e.g. spaces, punctuation).
- Printing all positions where the superhero appears.
- Optimizing memory use if the matrix is very large.
- Adding a validity check of the input and the dimensions of the matrix.
Solution 3 - Snail (recursion / backtracking, efficient)
This version uses recursion to read the matrix in a spiral and immediately searches for the superhero's name in the sentence. This way the search stops efficiently as soon as the required string of characters is found. This approach reduces memory use and makes it possible to find the first occurrence faster.
Steps of the solution:
- Read the matrix recursively in the "snail" pattern, adding characters to a string until you reach the end or until you find the superhero.
- For every added character, check whether the string ends with the required superhero name.
- If the name is found, record the position and stop further searching.
- If the name is not found after going through the whole matrix, -1 is printed.
Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, m;
vector<vector<char>> matrix;
string superhero;
int found_pos = -1;
// Function that recursively goes through the matrix in a spiral
void spiralDFS(int t, int b, int l, int r, string current) {
if (found_pos != -1) return; // stop if it has already been found
// We move right
for (int i = l; i <= r; i++) {
current.push_back(matrix[t][i]);
if (current.size() >= superhero.size() && current.substr(current.size() - superhero.size()) == superhero) {
found_pos = current.size() - superhero.size() + 1; // 1-based
return;
}
}
t++;
// We move down
for (int i = t; i <= b; i++) {
current.push_back(matrix[i][r]);
if (current.size() >= superhero.size() && current.substr(current.size() - superhero.size()) == superhero) {
found_pos = current.size() - superhero.size() + 1;
return;
}
}
r--;
// We move left
if (t <= b) {
for (int i = r; i >= l; i--) {
current.push_back(matrix[b][i]);
if (current.size() >= superhero.size() && current.substr(current.size() - superhero.size()) == superhero) {
found_pos = current.size() - superhero.size() + 1;
return;
}
}
b--;
}
// We move up
if (l <= r) {
for (int i = b; i >= t; i--) {
current.push_back(matrix[i][l]);
if (current.size() >= superhero.size() && current.substr(current.size() - superhero.size()) == superhero) {
found_pos = current.size() - superhero.size() + 1;
return;
}
}
l++;
}
// We call the function recursively for the inner spiral
if (t <= b && l <= r) spiralDFS(t, b, l, r, current);
}
int main() {
cin >> n >> m;
matrix.resize(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
cin >> superhero;
spiralDFS(0, n-1, 0, m-1, "");
cout << found_pos << endl;
return 0;
}
Comment on the solution:
This approach uses recursion to read the matrix in a spiral and at the same time checks whether the superhero's name is present. The advantage is that the search stops as soon as the required string is found, which makes the algorithm more efficient than the previous version, which first reads the whole matrix and only then looks for the name.
This version is especially suitable for larger matrices and longer strings, because it reduces memory use and execution time. It can easily be extended for additional requirements, such as ignoring irrelevant characters or searching for all occurrences.
Possible improvements:
- Adding an option to ignore spaces and punctuation during the search.
- Printing all positions where the superhero appears.
- Adapting it for very large matrices with memory optimization.
Back
|<Qualifications for district competitions
