深さ優先探索を用いたパズルの解法

###前提・実現したいこと
現在あるパズルを解いています。解けなくて困っています。
問題:
あるロボットは前後左右に動くことができます。12回移動するとき、考えられる移動経路は全部で何パターンありますか？ここでは、同じ場所を通らないとします。
例えば、3回移動する場合36通りあります。

###発生している問題・エラーメッセージ
配列が上手に更新できてないことが原因なのは理解しているんですが、それの解決方法が思いつかず悪戦苦闘しています。
###該当のソースコード

lang
1class Main{
2  private static int count = 0;    //移動経路の数
3  private static final int N = 3;  //移動回数
4  private static int[] xdirections ={1,0,-1,0}; //方向、右から時計回り
5  private static int[] ydirections ={0,1,0,-1};
6
7  public static void main(String[] args){
8      int[][] Map= new int[2*N+1][2*N+1];
9      Map[N][N] = 1;
10      Main m = new Main();
11      int step = 1;
12      count += m.dfs(N, N-1,Map,step); //真ん中の一つ上からスタート
13      System.out.println(count*4);  //結果出力
14  }
15  //深さ優先探索
16  int dfs(int x, int y , int[][] map,int step){
17    System.out.println("dfs("+x+","+y+")");
18    System.out.println("step "+ step );
19    map[y][x] = 1;
20    printMap(map);
21    if(step == N) {return 1;}
22    step++;
23    int counter = 0;
24    for(int i=0;i<4;i++){
25      int a = x + xdirections[i];
26      int b = y + ydirections[i];
27      if(check(a,b,map)){
28        counter += dfs(a,b,map,step);
29      }
30    }
31    return  counter;
32  }
33
34  boolean check(int x, int y,int[][] Map){
35    if(y > 2*N || y < 0 || x > 2*N|| x<0 ||Map[y][x] == 1){
36      return false;
37    }
38     return true;
39   }
40
41//確認用メソッド
42  void printMap(int[][] m){
43    for(int[] a : m){
44     for(int b : a){
45       System.out.print(b);
46     }
47       System.out.println(); 
48    }
49     System.out.println("\n");
50   }
51
52}

###補足情報(言語/FW/ツール等のバージョンなど)
言語はJavaです。
よろしくお願いします。

LouiS0616

2017/07/07 14:05

コードはバッククオート三つ```で囲み、インデントもつけて読みやすくしてください。よくわからない場合は、マークダウン記法を調べてみてください。

行動規範の内容に同意します

回答1件

ベストアンサー

ある経路を進んだ後別の経路から同じ場所を踏んでもいいので、ステップから戻る時にMapは0に戻してやらないといけないんじゃないかな？

Java
1int dfs(int x, int y , int[][] map,int step){
2    System.out.println("dfs("+x+","+y+")");
3    System.out.println("step "+ step );
4    map[y][x] = 1;
5    printMap(map);
6    if(step == N) {
7        map[y][x]=0;  // <- 追加
8        return 1;
9    }
10    step++;
11    int counter = 0;
12    for(int i=0;i<4;i++){
13      int a = x + xdirections[i];
14      int b = y + ydirections[i];
15      if(check(a,b,map)){
16        counter += dfs(a,b,map,step);
17      }
18    }
19    map[y][x] = 0;  // <- 追加
20    return  counter;
21  }