Untitled

 avatar
Darin
plain_text
a year ago
3.0 kB
4
Indexable
Never
// 5 ≤ N ≤ 20
// khi khởi tạo MAX_N + 2 = 22 và chỉ nhập liệu cho index 1 -> N, ta đảm bảo map được bao quanh bởi 4 viền là các số 0 - nước biển
// giá trị các ô của map (đất liền) là 1 -> 5
public void init(int N, int mMap[][]) {
	n = N;
	input = new int[MAX_N + 2][MAX_N + 2];
	output = new int[MAX_N + 2][MAX_N + 2];
	candidateMap = new HashMap<>(); //khởi tạo HashMap

	// nhập dữ liệu map
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			input[i + 1][j + 1] = output[i + 1][j + 1] = mMap[i][j];
		}
	}
	
	int tempHash = 0, reverseHash = 0;
	for (int len = 2; len <= 5; len++) {
		// 0 and 180 degrees
		for (int i = 1; i <= n; i++) {
			for (int j = 1; (j + len - 1) <= n; j++) {
				//calculate hash of structure of length "len"
				tempHash = 0;
				for (int k = 0; k + 1 < len; k++) {
					tempHash = (tempHash * 10)
							+ (input[i][j + k + 1] - input[i][j + k] + 5);
				}
				addToMap(tempHash, new Candidate(i, j, true, false)); //thêm mã băm và đối tượng Candidate vào HashMap
				//calculate reverse hash of structure of length "len"
				reverseHash = 0;
				for (int k = len - 1; k - 1 >= 0; k--) {
					reverseHash = (reverseHash * 10)
							+ (input[i][j + k - 1] - input[i][j + k] + 5);
				}
				//if both hashes are same don't add it to the map
				if (tempHash != reverseHash) {
					addToMap(reverseHash, new Candidate(i, j,
							true, true)); //thêm mã băm ngược và đối tượng Candidate vào HashMap
				}
			}
		}
		// 90 and 270 degrees 
		for (int i = 1; (i + len - 1) <= n; i++) {
			for (int j = 1; j <= n; j++) {
				//calculate hash of structure of length "len"
				tempHash = 0;
				for (int k = 0; k + 1 < len; k++) {
					tempHash = (tempHash * 10)
							+ (input[i + k + 1][j] - input[i + k][j] + 5);
				}
				addToMap(tempHash, new Candidate(i, j, false,
						false)); //thêm mã băm và đối tượng Candidate vào HashMap
				//calculate reverse hash of structure of length "len"
				reverseHash = 0;
				for (int k = len - 1; k - 1 >= 0; k--) {
					reverseHash = (reverseHash * 10)
							+ (input[i + k - 1][j] - input[i + k][j] + 5);
				}
				//if both hashes are same don't add it to the map
				if (tempHash != reverseHash) {
					addToMap(reverseHash, new Candidate(i, j,
							false, true)); //thêm mã băm ngược và đối tượng Candidate vào HashMap
				}
			}
		}
	}
}

public int numberOfCandidate(int M, int mStructure[]) {
	if (M == 1) {
		return n * n;
	}
	
    int hashKey = calculateHash(M, mStructure); //tính mã băm cho cấu trúc cho trước
    
    ArrayList<Candidate> candidates = candidateMap.get(hashKey); //lấy danh sách các đối tượng Candidate từ HashMap
    
    if(candidates == null) return 0; //nếu không có khóa nào khớp thì trả về số lượng là không
    
    return candidates.size(); //trả về số lượng các đối tượng Candidate trong danh sách
}

//phương thức để tính mã băm cho m