import java.util.Scanner ;public class Permutation{                           //求数字 1~n 的全排列；	int[] array ;	int[] book ;	int n ;	public void permutation(int step){          // 深度优先搜索思想；		if (step==n+1) {			for (int i=1;i<=n;i++) {				System.out.print(array[i] + " ") ;			}			System.out.println() ;		}else{			for (int i=1;i<=n;i++) {				if (book[i]==0) {					array[step] = i ;					book[i] = 1 ;					permutation(step+1) ;					book[i] = 0 ;				}			}		}	}	public static void main(String[] args){           //测试；		Permutation p = new Permutation() ;		Scanner sc = new Scanner(System.in) ;		System.out.println("please input an integer:") ;		p.n = sc.nextInt() ;		p.array = new int[p.n+1] ;		p.book = new int[p.n+1] ;		p.permutation(1) ;	}}

public class DepthFirstSearch{                                 //饱含深度优先搜索思想；	int[] array ;	int[] book ;	int n = 9 ;	int total ;	public void depthFirstSearch(int step){		if (step==n+1) {			if((array[1]+array[4]-array[7])*100+(array[2]+array[5]-array[8])*10+(array[3]+array[6]-array[9])==0){				total++ ;				for(int i=1;i<=n;i++){					System.out.print(array[i]) ;					if (i%3==0) {						System.out.print(" ") ;					}				}				System.out.println() ;			}		}else{			for(int i=1;i<=n;i++){                           //深度优先搜索思想核心；				if(book[i]==0){					array[step] = i ;					book[i] = 1 ; 					depthFirstSearch(step+1) ;					book[i] = 0 ;				}			}		}	}	public static void main(String[] args) {　　　　　　　　　//测试；　　　　　　　　　　　　　　　		DepthFirstSearch dfs = new DepthFirstSearch() ;		dfs.array = new int[dfs.n+1] ;		dfs.book = new int[dfs.n+1] ;		dfs.depthFirstSearch(1) ;		System.out.println(dfs.total/2) ;	}}

import java.util.Scanner ;public class HelpHL{	static int[][] map ;	static int[][] book ;	static int min = 99999999 ;	static int p ;	static int q ;	static int m ;	static int n ;		public static void dfs(int x, int y, int step){				if (x!=p || y!=q) {			int[][] next = {{1,0},{-1,0},{0,1},{0,-1}} ;       //四个方向；			for (int k=0;k<=3;k++) {				int newX = x + next[k][0] ;				int newY = y + next[k][1] ;				if (newX>=0 && newX<m && newY>=0 && newY<n) {					if (map[newX][newY]==0 && book[newX][newY]==0) {						book[newX][newY] = 1 ;						dfs(newX,newY,step+1) ;						book[newX][newY] = 0 ;					}				}			}		}else{			if(step<min){				min = step ;			}		}	}	public static void main(String[] args){		System.out.println("please input row(m) and column(n):") ;		Scanner sc = new Scanner(System.in) ;		m = sc.nextInt() ;		n = sc.nextInt() ;		map = new int[m][n] ;		book = new int[m][n] ;		System.out.println("please input destination (p,q):") ;		p = sc.nextInt() ;		q = sc.nextInt() ;		System.out.println("please input map barrier:") ;		for (int i=0;i<m;i++) {			for (int j=0;j<n;j++) {				map[i][j] = sc.nextInt() ;			}		}		System.out.println("please input initial position (startX,startY):") ;		int startX = sc.nextInt() ;		int startY = sc.nextInt() ;		dfs(startX,startY,0) ;		System.out.println("The minimum " + min + " steps") ;	}}