C++實現《江江的膜法陣》

#include<iostream>
#include<math.h>

using namespace std;

void Hashima(int*, int*, int*, int*, int*, int*, int*, int*, int*);

struct Point
{
    int x;
    int y;
};

int main(int argc, char** argv)
{
    int m, n, k1, k2, x = 0, y = 0, i = 1, result = 0;
    cout<<"Input n,m,k1,k2。"<<endl;
    do
    {
        cin>> n >> m >> k1 >> k2;
    }
    while(n * m % 2 != 0 || k1 < 0 || k2 < 0);
    int grid[n][m];
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            grid[i][j] = 0x00;
        }
    }
    Hashima(grid[0], &x, &y, &n, &m, &i, &k1, &k2, &result);
    cout<<"The result is:"<<result<<endl;
    cin.get();
    return 0;
}

Point FindHashima(int hashimaIndex, int* grid, int* n, int* m)
{
    Point hashima;
    for(int y = 0; y < *n; ++y)
    {
        for(int x = 0; x <= *m; ++x)
        {
            if(*(grid + y * *m + x) == hashimaIndex)
            {
                hashima.x = x;
                hashima.y = y;
            }
        }
    }
    return hashima;
}

void Hashima(int* grid, int* x, int* y, int* n, int* m, int* i, int* k1, int* k2, int* result)
{
    *(grid + *y * *m + *x) = *i;
    if(*i == *n * *m)
    {
        int maxXumingTime = 0, xumingTime;
        for(int hashimaA = 1; hashimaA <= *m * *n / 2; hashimaA++)
        {
            Point A = FindHashima(hashimaA, grid, n, m);
            Point B = FindHashima(hashimaA + *m * *n / 2, grid, n, m);
            xumingTime = *k1 * abs(A.y - B.y) + *k2 * abs(A.x - B.x);
            if(xumingTime > maxXumingTime)
            {
                maxXumingTime = xumingTime;
            }
        }
        if(*result == 0 || maxXumingTime < *result)
        {
            *result = maxXumingTime;
        }
    }
    else
    {
        if(*x + 1 <= *m - 1 && !(*(grid + *y * *m + *x + 1)))
        {
            *i += 1;
            *x += 1;
            Hashima(grid, x, y, n, m, i, k1, k2, result);
            *x -= 1;
            *i -= 1;
        }
        if(*y + 1 <= *n - 1 && !(*(grid + *y * *m + *x + *m)))
        {
            *i += 1;
            *y += 1;
            Hashima(grid, x, y, n, m, i, k1, k2, result);
            *y -= 1;
            *i -= 1;
        }
        if(*x - 1 >= 0 && !(*(grid + *y * *m + *x - 1)))
        {
            *i += 1;
            *x -= 1;
            Hashima(grid, x, y, n, m, i, k1, k2, result);
            *x += 1;
            *i -= 1;
        }
        if(*y - 1 >= 0 && !(*(grid + *y * *m + *x - *m)))
        {
            *i += 1;
            *y -= 1;
            Hashima(grid, x, y, n, m, i, k1, k2, result);
            *y += 1;
            *i -= 1;
        }
    }
    *(grid + *y * *m + *x) = 0;
    return;
}

在〈C++實現《江江的膜法陣》〉中有 1 則留言

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *