//
// Created by 高森森 on 2022/7/2.
//

#ifndef LEETCODE_SOLUTION60_H
#define LEETCODE_SOLUTION60_H
#define DIM 50

class Solution60 {
public:
    void ForwardDFS(char map[DIM][DIM],//输入的地图矩阵
            int row,int col,//行列的范围
            bool isright[DIM][DIM],//isright[i][j]标记起点与[i][j]是否可达
            int curR,int curC){
        if(isright[curR][curC]==1||map[curR][curC]=='#') {
            return ;
        }
        //标记节点可达，也可以说是标记已经遍历过的节点
        isright[curR][curC]= true;
        int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        if(map[curR][curC]=='#')
            return;
        if(map[curR][curC]=='-'){
            int c1=curC+direction[2][1];
            if(c1>=0)
                ForwardDFS(map,row,col,isright,curR,c1);
            c1=curC+direction[3][1];
            if(c1<col)
                ForwardDFS(map,row,col,isright,curR,c1);
        }
        if(map[curR][curC]=='|'){
            int c1=curR+direction[0][0];
            if(c1>=0)
                ForwardDFS(map,row,col,isright,c1,curC);
            c1=curR+direction[1][0];
            if(c1<row)
                ForwardDFS(map,row,col,isright,c1,curC);
        }
        if(map[curR][curC]=='|'){
            int c1=curR+direction[0][0];
            if(c1>=0)
                ForwardDFS(map,row,col,isright,c1,curC);
            c1=curR+direction[1][0];
            if(c1<row)
                ForwardDFS(map,row,col,isright,c1,curC);
        }
        if(map[curR][curC]=='.'){
           int c1=curR+direction[1][0];
            if(c1<row)
                ForwardDFS(map,row,col,isright,c1,curC);
        }

        if(map[curR][curC]=='+'||map[curR][curC]=='S'||map[curR][curC]=='T'){
            for(int i=0;i<4;i++){
                int r1=curR+direction[i][0];
                int c1=curC+direction[i][1];
                if(r1>=0&&r1<row&&c1>=0&&c1<col)
                {
                    ForwardDFS(map,row,col,isright,r1,c1);
                }
            }
        }
    }
    void backwardDFS(char map[DIM][DIM],
            int row,int col,
            bool isright[DIM][DIM],
            int curR,int curC,
            int preR,int preC)
    {
        if(isright[curR][curC]||map[curR][curC]=='#')
            return;
        if(map[curR][curC]=='.'&&preC==curC&&preR == curR+1){
            isright[curR][curC]= true;
        }
        if(map[curR][curC]=='-'&&preR==curR){
            isright[curR][curC]= true;
        }
        if(map[curR][curC]=='|'&&preC==curC){
            isright[curR][curC]= true;
        }
        if(map[curR][curC]=='+'||map[curR][curC]=='S'||map[curR][curC]=='T'){
            isright[curR][curC]= true;
        }
        if(isright[curR][curC]== false)
            return;
        int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        for(int i=0;i<4;i++){
            int r1=curR+direction[i][0];
            int c1=curC+direction[i][1];
            if(r1>=0&&r1<row&&c1>=0&&c1<col){
                backwardDFS(map,row,col,isright,r1,c1,curR,curC);
            }
        }
    }
};


#endif //LEETCODE_SOLUTION60_H