import java.util.*; public class Main { public static void main(String args[] ) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if(n<=0){System.out.print("NO"); return;} String str = sc.nextLine(); // change str into line List<Integer[]> list = new LinkedList(); int[][] Arr = new int[n][n]; for(int i =0;i<n;i++) { String strArr[] = sc.nextLine().split("\\s+"); for (int j = 0; j < strArr.length; j++) Arr[i][j] = Integer.parseInt(strArr[j]); } int k = sc.nextInt(); int m = Arr[0].length; Map<Integer,Integer> map = new HashMap(); // each position as a center, and find it int the circle/ use k as radius for(int i =0;i<n;i++) { map.clear(); // set-up the circle into the map for(int row=0; row < Math.min(n,i+k+1);row++){ for(int col = 0;col<Math.min(n,k+1);col++){ if(row == i && col == 0) continue; int key = Arr[row][col]; addMap(map, key); } } // mvoe for each i-th position for (int j = 0; j < Arr[0].length; j++) { // not, current i,j is not included int val = Arr[i][j]; if(map.containsKey(val)){ System.out.println("YES"); return; } map.put(val,1); // remove most left column and add most left row if(j+ 1< m) delMap(map,Arr[i][j+1]); if( j - k >=0 ){ // delete this 2k column for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){ delMap(map, Arr[row][j-k]); } } if( j + k +1 < m ){ // add this 2k column for(int row=Math.max(0,i-k); row < Math.min(n,i+k+1);row++){ addMap(map, Arr[row][j + k + 1]); } } } } System.out.println("NO"); } private static void addMap(Map<Integer,Integer> map, int val){ int count = 0; if(map.containsKey(val)) count = map.get(val); map.put(val,count+1); } private static void delMap(Map<Integer,Integer> map, int val){ if(map.containsKey(val)) { int count = map.get(val); if(count==1){ map.remove(val); }else map.put(val, count - 1); } } }
Friday, July 3, 2015
hackRand problem
Q: 检测一个2D数组 其 x,y坐标的k范围内是否存在重复
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment