package Dfs_Bfs;

import java.util.*;

//40min
public class beak_나이트의이동 {

	static class Pos{
		int x;
		int y;
		int cnt;
		
		Pos(int x,int y,int cnt){
			this.x =x;
			this.y =y;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n=sc.nextInt();
		
		for(int i=0;i<n;i++) {
			int m = sc.nextInt();
			int arr[][] = new int[m][m];
			
			sc.nextLine();
			
			Queue<Pos> qu = new LinkedList<>();
			String a[] = sc.nextLine().split(" ");
			qu.add(new Pos(Integer.parseInt(a[0]),Integer.parseInt(a[1]),0));
			arr[Integer.parseInt(a[0])][Integer.parseInt(a[1])] = 1;
			
			String b[] = sc.nextLine().split(" ");
			int endx = Integer.parseInt(b[0]); int endy = Integer.parseInt(b[1]);
			
			while(!qu.isEmpty()) {
				Pos now = qu.poll();
				int nowx = now.x;
				int nowy = now.y;
				
				if(nowx == endx && nowy == endy) {
					System.out.println(now.cnt);
					break;
				}
				
				int dx[] = {-2,-2,-1,-1, 1,1, 2,2};
				int dy[] = {-1, 1,-2, 2,-2,2,-1,1};
				
				for(int j=0; j<8; j++) {
					int nx = nowx + dx[j];
					int ny = nowy + dy[j];
					
					if(nx>=0&&nx<m &&ny>=0&&ny<m && arr[nx][ny]==0){
						arr[nx][ny] = 1;
						qu.add(new Pos(nx,ny,now.cnt+1));
					}
				}
				
			}//while
			
		}
	}
}

package Dynamic_programming;

import java.util.*;

public class prog_3_N으로표현 {

	static int answer = -1;
	public static void dfs(int n, int number, int cnt, int prev) {
		int temp = n; //

		if(cnt>8) // 8보다 커지면 -1
			return;
		
		if(number == prev) { //숫자가 같을 때
			System.out.println(cnt + " " + answer + " " + prev);
			if(answer == -1 || answer >cnt) //answer가 -1일때 최초로 바뀌는거니까 or answer가 cnt보다 클 떄
				answer = cnt;
			return;
		}
		
		for(int i=0; i<8-cnt; i++) {
			dfs(n,number, cnt+i+1, prev- temp);
			dfs(n,number, cnt+i+1, prev + temp);
			dfs(n,number, cnt+i+1, prev * temp);
			dfs(n,number, cnt+i+1, prev / temp);
			
			temp = temp*10 + n;
		}
		
	}
	
    public static int solution(int N, int number) {
    	
    	dfs(N,number,0,0);
        return answer;
    }
    
    public static void main(String[] args) {
		System.out.println(solution(5,12));
	}
}

package Dfs_Bfs;

import java.util.*;


//1h - half success
class Poos{
	int x;
	int y;
	int z;
	int day;
	
	Poos(int x, int y, int z, int day){
		this.x = x;
		this.y = y;
		this.z = z;
		this.day = day;
	}
	
}

public class beak_토마토2 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String n[] = sc.nextLine().split(" ");
		
		int y = Integer.parseInt(n[0]); // 열 -> 가로로 y개라는 뜻
		int x = Integer.parseInt(n[1]); // 행 -> 세로로 x개라는 뜻
		int z = Integer.parseInt(n[2]); // 높이
		
		int maze[][][] = new int[z][x][y]; // 맵에 데이터 넣기
		
		Queue<Poos> tomato = new LinkedList<>();
		
		//행개수만큼 넣고 -> 열 -> 높이
		for(int i=0;i<z;i++) {
			for(int j=0;j<x; j++) {
				//한줄씩 받아온거 행에 넣기 ->행 개수만큼
				String a[] = sc.nextLine().split(" ");
				for(int k=0;k<y; k++) {
					maze[i][j][k] =Integer.parseInt(a[k]);
					
					if(maze[i][j][k] == 1)
						tomato.add(new Poos(j,k,i,0));
				}//for - k
			}//for - j
		}//for - i
		
		int realday = 0;
		
		//bfs
		while(!tomato.isEmpty()) {
			Poos nowp = tomato.poll();
			realday = Math.max(realday, nowp.day);
			
			//꺼내서 6방향 살펴서 -> 0이면 1로만들고, tomato에 넣기
			int dx[] = {1,-1,0,0,0,0};
			int dy[] = {0,0,1,-1,0,0};
			int dz[] = {0,0,0,0,1,-1};
			
			for(int i=0; i<6;i++) {
				int nx = nowp.x + dx[i];
				int ny = nowp.y + dy[i];
				int nz = nowp.z + dz[i];
				
				if(nx>=0&&nx<x &&ny>=0&&ny<y &&nz>=0&&nz<z && maze[nz][nx][ny] == 0) {
					maze[nz][nx][ny] = 1; //익혀주고
					tomato.add(new Poos(nx,ny,nz, nowp.day+1));
				}
			}
		}
		
		boolean chk = false;
		
		for(int i=0;i<z;i++) {
			for(int j=0;j<x; j++) {
				for(int k=0;k<y; k++) {
					if(maze[i][j][k] == 0) {
						System.out.println("-1");
						chk=true;
						break;
					}
				}//for - k
			}//for - j
		}//for - i
		
		if(chk == false)
			System.out.println(realday);
		
	}
}

//https://fbtmdwhd33.tistory.com/33

package String;

import java.util.*;

public class beak_크로아티아알파벳 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String a = sc.next();
		//진짜 너무 바보같다..ㅎ 같은게 있으면 *로 치환하면 그만인 것을...
		
		String words[] = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
		
		for(int i=0;i<words.length; i++) {
			if(a.contains(words[i])) // 들어있는 모든 애들을 replace해준다! 한개만이 아니고!
				a = a.replaceAll(words[i], "*"); // replace()아니고 replaceAll()!!!!!!!!!!!!
				//그리고 치환했으면 반드시 다시 a 문자열에 넣어준다
		}
		
		System.out.println(a.length());
	}
}

package String;

import java.util.*;

public class beak_그룹단어체커 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int an = 0;
		
		sc.nextLine();
		
		for(int i=0;i<n; i++) {
			int arr[] = new int[26];
			boolean check = false;
			
			String a = sc.nextLine();
			
			for(int j=1; j<a.length(); j++) {
				
				arr[a.charAt(j-1)-'a'] = 1;
				
				if(a.charAt(j) != a.charAt(j-1)) {//나랑 전 단어가 같을 때는 상관 없고!! 나랑 전 단어가 다를 때, 내 전단어는 1표시 돼있고
												 //전 단어는 나랑 다르니까 새로운 내가 이미 전에 나왔었는지 확인해본다 
					if(arr[a.charAt(j)-'a'] !=0)
						check = true;
				}
			}
			
			if(check != true)
				an++;
			
		}//for
		
		System.out.println(an);
		
	}
}