Untitled

 avatar
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