Untitled
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