8

 avatar
unknown
c_cpp
a year ago
4.4 kB
18
Indexable
// #include <iostream>
// #include <cstring>
// using namespace std;
// void handleMem(char* a, char* b, char* c, char* d){
//     delete[] a; delete[] b; delete[] c; delete[] d;
// }
// bool solve(char** matrix, char* word, int n, int& sR, int& eR, int& sC, int& eC){
//     int len = strlen(word);
//     int aps = len - 1;
//     for(int i = 0; i < n; i++){
//         for(int j = 0; j < n; j++){
//             if(matrix[i][j] == word[0]){
//                 sR = i; sC = j;
//                 int c = 0;
//                 char* textRight = new char[n]; if(j + aps < n) {for(int k = j; k < n && c < len; k++) textRight[c++] =  matrix[i][k]; textRight[c] = '\0';} c = 0;
//                 char* textLeft = new char[n]; if(j - aps >= 0) {for(int k = j; k >= 0 && c < len; k--) textLeft[c++] = matrix[i][k]; textLeft[c] = '\0';} c = 0;
//                 char* textUp = new char[n]; if(i - aps >= 0) {for(int k = i; k >= 0 && c < len; k--) textUp[c++] = matrix[k][j]; textUp[c] = '\0';} c = 0;
//                 char* textDown = new char[n]; if(i + aps < n) {for(int k = i; k < n && c < len; k++) textDown[c++] = matrix[k][j]; textDown[c] = '\0';} c = 0;
//                 if(strncmp(textRight, word, len) == 0){
//                     eR = i;
//                     eC = j + len - 1;
//                     handleMem(textRight, textLeft, textUp, textDown);
//                     return true;
//                 }
//                 if(strncmp(textLeft, word, len) == 0){
//                     eR = i;
//                     eC = j - len + 1;
//                     handleMem(textRight, textLeft, textUp, textDown);
//                     return true;
//                 }
//                 if(strncmp(textUp, word, len) == 0){
//                     eR = i - len + 1;
//                     eC = j;
//                     handleMem(textRight, textLeft, textUp, textDown);
//                     return true;
//                 }
//                 if(strncmp(textDown, word, len) == 0){
//                     eR = i + len - 1;
//                     eC = j;
//                     handleMem(textRight, textLeft, textUp, textDown);
//                     return true;
//                 }
//                 handleMem(textRight, textLeft, textUp, textDown);
//             }
//         }
//     }
//     return false;
// }
// int main(){
//     int n;
//     cin >> n;
//     char** puzzle = new char*[n];
//     char word[11];
//     for(int i = 0; i < n; i++){
//         puzzle[i] = new char[n];
//         for(int j = 0; j < n; j++){
//             cin >> puzzle[i][j];
//         }
//     }
//     cin.get();
//     cin.getline(word, 11);
//     int startRow, endRow, startCol, endCol;
//     bool solved = solve(puzzle, word, n, startRow, endRow, startCol, endCol);
//     if(solved){
//         cout << startRow << ", " << startCol << " -> " << endRow << ", " << endCol << endl;
//     }else{
//         cout << "Not Found" << endl;
//     }
// }


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

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

bool dfs(char** board, int n, int r, int c, char* word, int k, int& eR, int& eC, int dr, int dc) {
    if (k == strlen(word)) {
        eR = r - dr;
        eC = c - dc;
        return true;
    }
    if (r < 0 || r >= n || c < 0 || c >= n || board[r][c] != word[k]) return false;
    return dfs(board, n, r + dr, c + dc, word, k + 1, eR, eC, dr, dc);
}

bool solve(char** board, char* word, int n, int& sR, int& eR, int& sC, int& eC) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {
                sR = i, sC = j;
                for (auto& d : directions) {
                    if (dfs(board, n, i, j, word, 0, eR, eC, d[0], d[1])) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    char** board = new char*[n];
    for (int i = 0; i < n; i++){
        board[i] = new char[n];
        for (int j = 0; j < n; j++) 
            cin >> board[i][j];
    }
            
    char word[11];
    cin.ignore();
    cin.getline(word, 11);

    int sR, sC, eR, eC;
    if (solve(board, word, n, sR, eR, sC, eC))
        cout << sR << ", " << sC << " -> " << eR << ", " << eC << endl;
    else
        cout << "Not Found" << endl;

    for(int i = 0; i < n; i++) delete board[i];
    delete[] board;
}
Editor is loading...
Leave a Comment