作业帮第三题AC
作业帮第三题,渣渣回报牛客一波,凭记忆写出来的,不知道是不是有错的地方,不过大概思想是这样
#include<iostream> #include<string> #include<vector> using namespace std; int n; int m; void dfs(const vector<string>& matrix,vector<vector<bool>> &fg, int i,int j,int &cur,int& ret) { cur++; if(cur > ret) ret = cur; fg[i][j] = true; if(i-1 >= 0 && fg[i-1][j] == false && matrix[i-1][j] == '1') dfs(matrix,fg,i-1,j,cur,ret); if(i+1 < n && fg[i+1][j] == false && matrix[i+1][j] == '1') dfs(matrix,fg,i+1,j,cur,ret); if(j-2 >= 0 && fg[i][j-2] == false && matrix[i][j-2] == '1') dfs(matrix,fg,i,j-2,cur,ret); if(j+2 < m && fg[i][j+2] == false && matrix[i][j+2] == '1') dfs(matrix,fg,i,j+2,cur,ret); return; } int main() { vector<string> matrix; string str; while(cin >> str) { matrix.push_back(str); } n = matrix.size(); if(n == 0) { cout << 0 << endl; return 0; } m = matrix[0].size(); vector<vector<bool>> flag(n,vector<bool>(m,false)); int ret = 0; int cur = 0; for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { if(matrix[i][j] == '1' && flag[i][j] == false) { dfs(matrix,flag,i,j,cur,ret); cur = 0; } } } cout << ret << endl; return 0; }