[BOJ] 17070. 파이프 옮기기 1

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
   static Scanner sc=new Scanner(System.in);
   static int N,cnt;
   static int map[][];
   static boolean visited[][];
   static int dx[][]={ {0,1},{0,1,1},{1,1}};
   static int dy[][]={ {1,1},{1,1,0},{0,1}};
   static List<Point> list=new ArrayList<>();
   
   public static void main(String[] args) {
      N=sc.nextInt();
      map=new int[N][N];
      visited=new boolean [N][N];
      cnt=0;
      
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            map[i][j]=sc.nextInt();                  
         }
      }
      
      go(0,1,0,0);

      System.out.println(cnt);
                  
   }
   
   public static void go(int x,int y,int d,int state) {
      if(x<0 || y<0 || x>N-1 || y>N-1) return;
      if(map[x][y]==1) return;
      if(state==1 && (map[x-1][y]==1 || map[x][y-1]==1)) {
         return;
      }
      if(x==N-1 && y==N-1) {
         cnt++;
//         int size= list.size();
//         for (int i = 0; i < size; i++) {
//            if(list.get(i).x==0 && list.get(i).y==1) {
//               System.out.println();
//            }
//            System.out.print(list.get(i));         
//         }
         return;
      }
      if(!visited[x][y]) {
         visited[x][y]=true;
         list.add(new Point(x,y,state));
         if(state==0) {
            for (int i = 0; i < dx[state].length; i++) {
               go(x+dx[state][i],y+dy[state][i],d+1,state+i);                                          
            }
         }else if(state==1) {
            for (int i = 0; i < dx[state].length; i++) {
               if(x==1 && y==3) {
                  int a=0;
               }
               go(x+dx[state][i],y+dy[state][i],d+1,i);            
            }
         }else {
            for (int i = 0; i < dx[state].length; i++) {
               if(state==3) {
                  int b=0;
               }
               go(x+dx[state][i],y+dy[state][i],d+1,state-i);            
            }
         }
         visited[x][y]=false;
         list.remove(list.size()-1);
      }
   }
   
   static class Point {
      int x,y,s;
      Point(int x,int y,int s){
         this.x=x;
         this.y=y;
         this.s=s;
      }
      
      public String toString() {
    	 if(s==0) {
    		 return "Point [x=" + x + ", y=" + y+ ", state= 가로"+ "]\n";
    	 }else if(s==1) {
    		 return "Point [x=" + x + ", y=" + y+ ", state= 대각선"+ "]\n";
    	 }else {
    		 return "Point [x=" + x + ", y=" + y+ ", state= 세로"+ "]\n";
    	 }
      }
   }
}