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