Сопоставление строки с заданным двумерным массивом символов - PullRequest
Новая
       17

Сопоставление строки с заданным двумерным массивом символов

2 голосов
/ 14 апреля 2019

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

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

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

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

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

ОБРАЗЕЦ ВХОДА 1 3 3 аба хуг BDR axbaydb

ОБРАЗЕЦ ВЫХОДА Да

Мы выбираем «a» из строки 1. Теперь мы можем выбрать только еще одну «a» из строки 1, поскольку одна «a» уже используется. Аналогично, «х» из строки 2, «б» из строки 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

1 Ответ

1 голос
/ 14 апреля 2019

Любая причина, почему вы не можете просто использовать векторные и строковые классы в своих интересах вместо всего этого ручного malloc's и разбора 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)
        {
            string& currentRow = rows[rowIndex];
            if (currentRow.find(c) == string::npos)
            {
                allFound = false;
                break;
            }
            rowIndex = (rowIndex + 1) % row;
        }
        cout << (allFound ? "Yes" : "No") << endl;
    }
    return 0;
}
...