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