小面智行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;
} #笔试##小马智行#

