# DFS

假設有一個地圖M*N這麼大(M跟N是題目會給,陣列不能這樣設)

int map[M][N]={0};

假設題目問你從地圖的(1,1)到(i,j)有幾條路可以走
首先先呼叫一個funtion然後把起始點傳進去

#include <stdio.h>
int i,j,M,N;
int ans=0;

int funtion(int ,x,int y){

}

int main(){
    scanf("%d %d %d %d",&M,&N,&i,&j);
    funtion(1,1);
}

funtion裡面是要遞迴上下左右能走的位置
就是把能走的都過一遍
(要檢查邊界)

int funtion(int x,int y){
    if(x<=0||y<=0||x>M||y>n) return 0;
    funtion(x+1,y);
    funtion(x-1,y);
    funtion(x,y+1);
    funtion(x,y-1);
    return 0;
}

但因為走過的路就不能再走了所以要設一個used陣列記錄哪格已經走過了

int used[M][N]={0};

fumtion:

int funtion(int x,int y){
    if(x<=0||y<=0||x>M||y>N) return 0;
    if(used[x][y]==1) return 0;//如果這格已經用過了就return 0,不繼續遞迴
    used[x][y]=1;
    funtion(x+1,y);
    funtion(x-1,y);
    funtion(x,y+1);
    funtion(x,y-1);
    return 0;
}

最後就剩判斷是否已經走到終點了

int funtion(int x,int y){
    if(x<=0||y<=0||x>M||y>N||used[x][y]==1) return 0;
    if(x==i&&y==j){
        ans++;//找到一種走法,把答案+1
        return 0;//結束遞迴
    }
    used[x][y]=1;
    funtion(x+1,y);
    funtion(x-1,y);
    funtion(x,y+1);
    funtion(x,y-1);
    return 0;
}

最後要在return之前把used設回0

int funtion(int x,int y){
    if(x<=0||y<=0||x>M||y>N) return 0;
    if(used[x][y]==1) return 0;
    if(x==i&&y==j){
        ans++;
        return 0;
    }
    used[x][y]=1;
    funtion(x+1,y);
    funtion(x-1,y);
    funtion(x,y+1);
    funtion(x,y-1);
    used[x][y]=0;
    return 0;
}

完正程式碼:

#include <stdio.h>

int i,j,M,N;
int ans=0;
int used[100][100]={0};

int funtion(int x,int y){
    if(x<=0||y<=0||x>M||y>N||used[x][y]==1) return 0;
    if(x==i&&y==j){
        ans++;
        return 0;
    }
    used[x][y]=1;
    funtion(x+1,y);
    funtion(x-1,y);
    funtion(x,y+1);
    funtion(x,y-1);
    used[x][y]=0;
    return 0;
}

int main(){
    scanf("%d %d %d %d",&M,&N,&i,&j);
    funtion(1,1);
    printf("%d\n",ans);
    return 0;
}

題目我隨便舉的啦,概念大概是這樣,dfs的題目真的超難找,大部分都bfs

e431:

#include <stdio.h>
#include <string.h>

int n,m;
int used[10][10];
int ans;

int dfs(int x,int y,int cnt){
  if(x>=n||x<0||y>=m||y<0||used[x][y]==1) return 0;
  if(cnt==n*m){
    ans++;
    return 0;
  }
  used[x][y]=1;
  dfs(x+1,y,cnt+1);
  dfs(x-1,y,cnt+1);
  dfs(x,y+1,cnt+1);
  dfs(x,y-1,cnt+1);
  used[x][y]=0;
  return 0;
}

int main(){
  while(EOF!=scanf("%d %d",&n,&m)){
    ans=0;
    for(int i=0;i<n;i++){
      for(int k=0;k<m;k++){
        memset(used,0,sizeof(used));
        dfs(i,k,1);
      }
    }
    printf("%d\n",ans/2);
  }
  return 0;
}