小面智行9.16笔试,第二题,谁帮我看看代码,只过了30

给一个m*n的矩阵,矩阵中含有上下左右四个符号,只能按照符号行进,求最多能走的不同栅格个数

#include<iostream>
#include<vector>

using namespace std;

int dfs(vector<vector<char>>& map, vector<vector<int>>& dp, vector<vector<int>>& visited, int i, int j) {
    if (dp[i][j] != 0) {
        return dp[i][j];
    }
    dp[i][j]++;
    visited[i][j] = 1;
    if (map[i][j] == '^') {
        if (i - 1 >= 0 && visited[i - 1][j] != 1)
            dp[i][j] += dfs(map, dp, visited, i - 1, j);
    }
    else if (map[i][j] == 'v') {
        if (i + 1 < map.size() && visited[i + 1][j] != 1)
            dp[i][j] += dfs(map, dp, visited, i + 1, j);
    }
    else if (map[i][j] == '>') {
        if (j + 1 < map[0].size() && visited[i][j + 1] != 1)
            dp[i][j] += dfs(map, dp, visited, i, j + 1);
    }
    else if (map[i][j] == '<') {
        if (j - 1 >= 0 && visited[i][j - 1] != 1)
            dp[i][j] += dfs(map, dp, visited, i, j - 1);
    }
    return dp[i][j];
}

int main() {
    int row;
    cin >> row;
    int column;
    cin >> column;
    vector<vector<char>> map;
    char dirt;
    for (int i = 0; i < row; i++) {
        vector<char> temp;
        for (int j = 0; j < column; j++) {
            cin >> dirt;
            temp.push_back(dirt);
        }
        map.push_back(temp);
    }
    vector<vector<int>> dp(row, vector<int>(column, 0));
    vector<vector<int>> visited(row, vector<int>(column, 0));
    int max_len = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            vector<vector<int>> visited(row, vector<int>(column, 0));
            dp[i][j] = dfs(map, dp, visited, i, j);
            if (dp[i][j] > max_len) {
                max_len = dp[i][j];
            }
        }
    }
    cout << max_len << endl;
    return 0;
}

#笔试##小马智行#
全部评论
同学同花顺尝试一下吗,面试简单不造火箭,我帖子有内推
点赞 回复 分享
发布于 2022-09-17 00:44 浙江

相关推荐

10-31 14:54
已编辑
门头沟学院 算法工程师
点赞 评论 收藏
分享
评论
点赞
1
分享
牛客网
牛客企业服务