8
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