package backjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 사다리조작15684 { public static int n; public static int m; public static int h; public static int flag; public static String idx; public static void main(String args[]) throws IOException { BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st= new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); m=Integer.parseInt(st.nextToken()); h=Integer.parseInt(st.nextToken()); boolean[][] map=new boolean[h][n]; int[] arr=new int[n]; for (int i = 0; i < m; i++) { st=new StringTokenizer(br.readLine()); int x=Integer.parseInt(st.nextToken())-1; int y=Integer.parseInt(st.nextToken())-1; map[x][y]=true; arr[y]++; } flag=0; int sum=0; idx=""; for (int i = 0; i < arr.length; i++) { arr[i]%=2; sum+=arr[i]; if(arr[i]>0) { idx+=i; } } if(sum<4) { if(dfs(map,sum,0)) { System.out.println(sum+flag); return; } System.out.println(-1); }else { System.out.println(-1); } } public static boolean dfs(boolean[][] map,int sum,int now) { if(now==sum) { if(checkMap(map)) { return true; } if(sum<=1&& inputDouble(map,0,0)) { flag=2; return true; } return false; } int x=idx.charAt(now)-'0'; for (int i = 0; i < h; i++) { if(!map[i][x]&&inputCheck(map, i, x)) { map[i][x]=true; if(dfs(map,sum,now+1)) { return true; } map[i][x]=false; } } return false; } public static boolean inputDouble(boolean[][] map,int now, int y) { if(now==2) { return checkMap(map); } for (int i = 0; i < h; i++) { if(!map[i][y]&&inputCheck(map, i, y)){ map[i][y]=true; if(inputDouble(map,now+1,y)) { return true; } map[i][y]=false; } } if(y0&&map[x][y-1])return false; if(y0&&map[j][idx-1]) { idx--; } } if(idx!=i) { return false; } } return true; } }

제출 #111525

제출 정보

제출 결과

제출 코드

찾은 반례