DFS

#include <iostream>
#include <cmath>
#include <string>
#include <fstream>

using namespace std;

/* 问题: 从所有可行的起点开始,得到的是多条路径长度的最值,但是得不到所有经过的节点数目
* 解决: 最优子结构定义错误
*/

const int ROW = 3, COL=3;
const int map[ROW][COL] = {0,1,1,
                           1,1,1,
                           0,1,0};

int dfs(int i, int j, int flag[ROW][COL]){
    flag[i][j] = 1;
    int num = 1;
    int tmp = 0;
    int num1=0, num2=0,num3=0,num4=0;
    if(i+1<ROW && map[i+1][j] && !flag[i+1][j]){
        num1 = dfs(i+1,j, flag);
    }
    if(i-1>=0 && map[i-1][j] && !flag[i-1][j]){
        num2 = dfs(i-1,j, flag);
    }
    if(j+1<COL && map[i][j+1] && !flag[i][j+1]){
        num3 = dfs(i,j+1, flag);
    }
    if(j-1>=0 && map[i][j-1] && !flag[i][j-1]){
        num4 = dfs(i,j-1, flag);
    }
    num += num1 + num2 + num3 + num4;
//    flag[i][j] = 0;
    return num;
}

int main(){
    int flag[ROW][COL] = {0,0,0,
                      0,0,0,
                      0,0,0};

    int num = 0;
    for(int i=0;i<ROW;i++){
        for(int j=0;j<COL;j++){
            if(!flag[i][j] && map[i][j]){
                int tmp = dfs(i,j,flag);
                cout << i << " "<< j << " " << tmp << endl;
                num = num>tmp?num:tmp;
            }
        }
    }
    cout << num << endl;
    return 0;
}