Блог

Вам дается матрица символов. Матрица состоит из N строк и M столбцов. Учитывая строку s, вы должны указать, возможно ли сгенерировать эту строку из заданной матрицы. Правила для генерации строки из матрицы следующие:

Вы должны выбрать первый символ строки из строки 1, второй символ из строки 2 и так далее. N 1-й символ строки должен быть выбран из строки 1, то есть вы можете перемещаться по строкам циклическим образом (строка 1 идет после строки N). Если вхождение символа выбрано из строки, вы не сможете снова выбрать то же самое вхождение из этой строки. Вы должны напечатать Yes, если данная строка может быть сгенерирована из матрицы с использованием заданных правил, иначе выведите No .

Формат ввода:

Первая строка состоит из T, обозначающего количество тестовых примеров. Каждый тестовый пример состоит из: Первая строка состоит из двух целых чисел N и M, обозначающих размеры матрицы. Следующие N строк состоят из M символов каждая. Последняя строка состоит из строки s.

Формат вывода: для каждого тестового примера выведите «Да», если строка может быть сгенерирована, иначе выведите «Нет». Ответ для каждого тестового примера должен быть в новой строке.

ПРИМЕР ВВОДА 1 3 3 aba xyz bdr axbaydb

ПРИМЕР ВЫВОДА Да

Мы выбираем «a» из строки 1. Теперь мы можем выбрать только еще один «a» из строки 1, поскольку один «a» уже используется. Аналогично, «x» из строки 2, «b» из строки 3. Теперь мы снова возвращаемся к строке 1. Мы выбираем «a» из строки 1, «y» из строки 2 и так далее.

 #include<iostream>
#include<string>
using namespace std;

int main()
{
int testcase, row, col, x = 0, i = 0;
bool flag = true;
string word;
cin >> testcase; //number of testcases
for (int i = 0; i < testcase; i  )
{
    cin >> row;  //number of rows
    cin >> col;  //number of columns

    char** arr = (char**)malloc(row * sizeof(char *)); //allocating memory for arr pointer to pointer based on the number of rows

    for (int i = 0; i < row; i  )
    {
        arr[i] = (char*)malloc(col * sizeof(char)); //allocating memory for arr pointer 
    }
    for (int i = 0; i < row; i  )
    {
        for (int j = 0; j < col; j  )
        {
            cin >> arr[i][j];
        }
    }
    cin>>word;
    while (x < word.length()) // looping through the given string until it reaches the end of the string
    {
        while (i <= row) // looping through the rows of the 2darray
        {
            for (int j = 0; j < col; j  ) //looping through each element in 1d array
            {
                if (i == row) //to ensure that after the last row it goes back again to the first row and starts iterating from the first row
                {
                    i = 0;
                }
                if (word[x] == arr[i][j]) // if character from the string matches the element in the 1st row of 2d array, we will go to the next character of the string and also go to the next row for searching the character in that row.
                {
                    x  ;
                    i  ;
                }
                else
                {
                    flag = false; // if the value is not found, we will set the flag to false
                }
            }
        }
    }
    if (flag == false)
    {
        cout << "No"<<endl;
    }
    else
    {
        cout << "Yes"<<endl;
    }
}
return 0;
 

}

Следующий код работает не так, как ожидалось

 1
5 8
wxyqkbtk
xpbzexmh
ffkgmqnj
lfyrrwsn
vqfftarq
tswsgdzlpfxithvahmrffgax
 

Есть ли причина, по которой вы не можете просто использовать векторные и строковые классы в своих интересах вместо всего этого ручного malloc’ing и синтаксического анализа char по char?

 #include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
    int testcase, row, col;
    cin >> testcase;
    for (int i = 0; i < testcase; i  )
    {
        vector<string> rows;
        string word;
        bool allFound = true;
        int rowIndex = 0;

        cin >> row;
        cin >> col;  // you can ignore this value since we read each row as a string

        // read each row and append to the "rows" vector
        for (int r = 0; r < row; r  )
        {
            string line;
            cin >> line;
            rows.push_back(line);
        }

        // read the test case word    
        cin >> word;

        // for each letter in word, test to see if that same letter
        // exists on the expected row of input
        for (char c : word)
        {
            stringamp; currentRow = rows[rowIndex];
            if (currentRow.find(c) == string::npos)
            {
                allFound = false;
                break;
            }
            rowIndex = (rowIndex   1) % row;
        }
        cout << (allFound ? "Yes" : "No") << endl;
    }
    return 0;
}