本地正确牛客不对

矩阵中的路径

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;
}
全部评论
bool visited[100];要进行初始化,在本地执行的时候,没有初始化的话在if语句中判断,为真;但是在牛客中可能不是这种情况,你把visited用循环初始化一下,估计就没问题了
点赞 回复 分享
发布于 2020-03-02 20:39

相关推荐

10-16 22:56
门头沟学院 C++
1234567800:歌尔今年给211开14-15k吗,我本地人连面试都不给😂
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务