本地正确牛客不对
矩阵中的路径
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;
}


