回溯使用感染函数实现
思路，假设已经有感染函数，然后遍历数组，当遇到1的时候就能将上下左右是1的都变成2，然后继续遍历如果遇到继续执行感染函数即可，直到遍历完毕。
#include<iostream> #include<vector> using namespace std; class Solution { private: int direction[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };//顺时针方向 bool isArea(int i, int j, int row, int col) { return i >= 0 && i < row && j >= 0 && j < col; } void infected(vector<vector<int>>&input, int i, int j, int row, int col) { for (int k = 0; k < 4; ++k) { int new_x = i + direction[k][0]; int new_y = j + direction[k][1]; if (isArea(new_x, new_y, row, col)&&input[new_x][new_y]==1) {//判断是否有效并且该位置恒为1 input[new_x][new_y] = 2; infected(input,new_x, new_y, row, col); } } } public: int countIsland(vector<vector<int>>&input) { if (input.size() == 0) return 0; int count = 0; int row = input.size(); int col = input[0].size(); for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (input[i][j] == 1) { count++; input[i][j] = 2; infected(input, i, j, row, col); } } } return count; } }; int main() { vector<vector<int>> m = { {0,0,1,0,1,0}, {1,1,1,0,1,0}, {1,0,0,1,0,0}, {0,0,0,0,0,0} }; Solution* ptr = new Solution(); int res = ptr->countIsland(m); cout << res << endl; while (1); }
