本地正确牛客不对
矩阵中的路径
http://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
就是普通的回溯啊
#include<iostream> using namespace std; bool visited[100]; bool hasPathCore(char* matrix, int rows, int cols, int size, char* str, int i, int& k) { visited[i] = true; int l = i - 1; int r = i + 1; int u = i - cols; int d = i + cols; ++k; if (matrix[i] != str[k]) return false; if (l >= 0&&!visited[l]) { hasPathCore(matrix, rows, cols, size, str, l, k); if (k == strlen(str) - 1) { return true; } visited[l] = false; --k; } if (r <= size - 1&&!visited[r]) { hasPathCore(matrix, rows, cols, size, str, r, k); if (k == strlen(str) - 1) return true; visited[r] = false; --k; } if (u >= 0&&!visited[u]) { hasPathCore(matrix, rows, cols, size, str, u, k); if (k == strlen(str) - 1) return true; visited[u] = false; --k; } if (d <= size - 1&&!visited[d]) { hasPathCore(matrix, rows, cols, size, str, d, k); if (k == strlen(str)-1) return true; visited[d] = false; --k; } } bool hasPath(char* matrix, int rows, int cols, char* str) { int k = -1, size = rows*cols; int &ka = k; for (int i = 0; i < size; ++i) { if (!hasPathCore(matrix, rows, cols, size, str, i, ka)) { visited[i] = false; --ka; continue; } else break; } cout << k << endl; if (k == strlen(str) - 1) return true; return false; } int main() { char* matrix = new char[13]{ 'A', 'B', 'C', 'E', 'S', 'F', 'C', 'S', 'A', 'D', 'E', 'E' }; int rows = 3, cols = 4; char* str = new char[7]{ 'A', 'B', 'C', 'C','E','D'}; bool r = hasPath(matrix, rows, cols, str); cout << r << endl; return 0; }