軍隊における符号化アルゴリズム27

ナビゲーションパス(DFS)

やっぱり久しぶり…最近すべてのコメントが久しぶりにアップされました.ハハハ...
最近休暇に出かけましたが、最後の休暇かもしれません.今は4ヶ月ぐらいしか残っていないので、できるだけ早く退役する時になりました.
本当に生意気な先日のような熱い学究熱(?)真面目に符号化するという考えがありましたが、なかなか難しいです.残り4ヶ月も頑張ります.
まず経路探索です.
方向図がある場合は、プログラムを作成して1番からN番までのすべてのパスの指数を出力します.
1行目には、頂点数N(1<=N<=20)と、幹線数Nが与えられる.そして、M行の間に接続情報が与えられる.
まず似たようなアルゴリズム,機械論の問題である.今までのDFSに近いのと似ていて、私が探していた答えはifドアにあります.そうしないとelseに釘付けになって、左と右の子供を通じて得た答えにだんだん近づいてきます.
本当に基本中の基本的な問題です

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int map[21][21]={0,}, ch[10]={0,};
//ch배열을 만들어줌으로써 내가 한번 갔었던 경로를 기억해야 한다.
int M, N, cnt=0;

void DFS(int v){
    
    if(v==N){
        cnt++;
        return;
    } 
    else{
        
        for(int i=1; i<=N; i++){
            if(map[v][i]==1 && ch[i]==0){
            //맵에 길이 있고, ch배열도 0일 경우 갈 수 있음
                ch[i]=1;
                DFS(i);
                ch[i]=0;
                //ㄴ요놈들이 핵심! 
            }
        }
        
    }
}

int main(){
    
    int a, b;
    
    cin>>N;
    cin>>M;
    
    for(int i=1; i<=M; i++){
        cin>>a;
        cin>>b;
        map[a][b]=1;
    }
    
    ch[1] = 1;
    
    DFS(1);
    
    cout<<cnt;
}

今回の問題は上の問題より少し深くなって、本当に愚かな行為なので、昨日は全部解けたのに、答えがおかしくて、今日まで.
まず問題は.

これです.これもmap二層配列とch配列で、道路が通っているところと私が通っているところのch配列をチェックして、東西南北を確認しながら探索すればいいのです.
でも本当に.main関数側はcinを2回受け入れたので、いつも変な数万の答えが出てきます...ああ...
とにかく、これは難しくない問題です.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int map[8][8]={0,}, ch[8][8]={0,};
int cnt=0;

void DFS(int a, int b){
    
    if(a==7 && b ==7){
        cnt++;
        return;
    } 
    else{
        
        if(map[a+1][b]==0 && ch[a+1][b]==0){
            ch[a+1][b]=2;
            DFS(a+1, b);
            ch[a+1][b]=0;
        }
        if(map[a][b+1]==0 && ch[a][b+1]==0){
            ch[a][b+1]=2;
            DFS(a, b+1);
            ch[a][b+1]=0;
        }
        if(map[a-1][b]==0 && ch[a-1][b]==0){
            ch[a-1][b]=2;
            DFS(a-1, b);
            ch[a-1][b]=0;
        }
        if(map[a][b-1]==0 && ch[a][b-1]==0){
            ch[a][b-1]=2;
            DFS(a, b-1);
            ch[a][b-1]=0;
        }
        
    }
}

int main(){
    

    for(int i=1; i<=7; i++){
        for(int j=1; j<=7; j++){
            cin>>map[i][j];
            //cin>>ch[i][j];
            //하아.. 이부분 때문에 진짜 개고생.. 진짜 난 바보새끼..
        }
    }
    
    for(int i=1; i<=7; i++){
        map[0][i] = 1;
        map[i][0] = 1;
        ch[0][i] = 1;
        ch[i][0] = 1;
    }
    
    
    ch[1][1] = 2;//한번 지나간 길은 2
    
    DFS(1, 1);
    
    cout<<cnt;
}

次のコードは上のコードをよりきれいに整理します.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int map[8][8]={0,}, ch[8][8]={0,};
int cnt=0;
int dir_a[5] = {0, 1, 0, -1}, dir_b[5] = {1, 0, -1, 0};


void DFS(int a, int b){
    int xx, yy;
    if(a==7 && b ==7){
        cnt++;
        return;
    } 
    else{
        
        for(int i=0; i<4; i++){
            xx = a + dir_a[i];
            yy = b + dir_b[i];
            if(xx<1 || xx>7 || yy<1 || yy>7) continue;
            
            if(map[xx][yy]==0 && ch[xx][yy]==0){
                ch[xx][yy]=1;
                DFS(xx, yy);
                ch[xx][yy]=0;
            }
        }
        
    }
}

int main(){
    

    for(int i=1; i<=7; i++){
        for(int j=1; j<=7; j++){
            cin>>map[i][j];
            cin>>ch[i][j];
        }
    }
    
    
    ch[1][1] = 1;//한번 지나간 길은 2
    
    DFS(1, 1);
    
    cout<<cnt;
}