Untitled
unknown
plain_text
a year ago
2.7 kB
7
Indexable
#define MAX_N (10000) #define MAX_M (10) struct Node { struct Node* left; struct Node* right; int val; Node() { left = right = nullptr; val = 0; } void init() { if (left != nullptr) { left->init(); left = nullptr; } if (right != nullptr) { right->init(); right = nullptr; } val = 0; delete this; } void push_back(int idx) { if (val == 0) val = idx; } }; Node* root; int n, m; void init(int N, int M, char mImage[MAX_N][MAX_M][MAX_M]) { if(root != nullptr) root->init(); n = N; m = M; root = new Node(); for (int i = 0; i < n; i++) { Node* it = root; for (int y = 0; y < m; y++) { for (int x = 0; x < m; x++) { if (mImage[i][y][x] == 0) { if (it->left == nullptr) { it->left = new Node(); } it = it->left; } else { if (it->right == nullptr) { it->right = new Node(); } it = it->right; } } } it->push_back(i + 1); } } char arr[105]; int d[100005]; int dfs(Node* cur, int pos, int diff) { if (cur == nullptr || diff >= 3) return 0; if (pos == m * m) { if (cur->val != 0) { d[cur->val] = diff; return cur->val; } return 0; } int left_node = 0; int right_node = 0; if (arr[pos] == 0) { left_node = dfs(cur->left, pos + 1, diff); right_node = dfs(cur->right, pos + 1, diff + 1); } else { left_node = dfs(cur->left, pos + 1, diff + 1); right_node = dfs(cur->right, pos + 1, diff); } if (left_node == 0 || d[left_node] > d[right_node] || (d[left_node] == d[right_node] && left_node > right_node)) return right_node; return left_node; } int findImage(char mImage[MAX_M][MAX_M]) { for (int y = 0; y < m; y++) { for (int x = 0; x < m; x++) { arr[y * m + x] = mImage[y][x]; } } d[0] = m * m; int ret= dfs(root, 0, 0); return ret; }
Editor is loading...
Leave a Comment