ルームメイトは最近STEAMのLYNEというゲームに夢中している

 

ルールは簡単である：スタートからエンドまで同じ色な菱形をひとつのラインで繋ぐ

その難点は白い菱形のホールを最後の時に全て占用しなければいけないこと

だから、状況によって時々とっても難しいパゾルになることもある

 

それでこのパゾル等を解けるためにひとつのプログラムを書きた

とても簡単で最適化されることもなかったプログラムなので、難しいパゾルなら時々多くの時間を掛かるかも知れない欠点があるけど(/ω＼*)

#include<iostream>
#include<string>
#include<memory.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define MAXLINK 650
using namespace std;

char square[20][20];
int sizex, sizey;
typedef int8_t link[4];
link links[MAXLINK];
bool letters[30];
clock_t t_start, t_end;

// Common Functions
char toSmall(char toConvert)
{
    return (char)(toConvert + 32);
}

int toNum(char num)
{
    return num - '0';
}

int8_t abs(int8_t origin)
{
    if(origin >= 0)
        return origin;
    else
        return -origin;
}

int8_t toSeq(char lt)
{
    return lt - 'A';
}

char toLetter(int8_t k)
{
    return k + 'A';
}

// Way-Searching Functions
void startNew(char lt);
bool availability(char lt, int8_t xNow, int8_t yNow, int8_t xStep, int8_t yStep);
bool finishLetter(char lt);
bool finishHole();
void getOutput();

void nextStep(char lt, int8_t xNow, int8_t yNow, bool startPoint)
{
    //cout<<(int)xNow<<" "<<(int)yNow<<endl;
    if(!startPoint)
    {
        // Whether there's a step could be taken
        bool nextStepAvail = false;
        for(int8_t yStep = -1; yStep <= 1; yStep++)
        {
            for(int8_t xStep = -1; xStep <=1; xStep++)
            {
                if(xStep == 0 && yStep == 0)
                    continue;
                if(availability(lt, xNow, yNow, xStep, yStep))
                {
                    nextStepAvail = true;
                    break;
                }
            }
            if(nextStepAvail)
                break;
        }

        if(!nextStepAvail || (square[xNow][yNow] >= 'A' && square[xNow][yNow] <= 'Z'))
        {
            // Stops at a hole
            if(square[xNow][yNow] >= '0' && square[xNow][yNow] <= '8')
                return;
            // Stops at a color block which is not an endpoint
            if(square[xNow][yNow] >= 'a' && square[xNow][yNow] <= 'z')
                return;
            // Stops at an endpoint
            if(square[xNow][yNow] >= 'A' && square[xNow][yNow] <= 'Z')
            {
                // Now at an endpoint but the color unfinished
                if(!finishLetter(square[xNow][yNow]))
                    return;
                // A whole path of the color finished
                // Check if there're other colors
                int8_t k = toSeq(lt) + 1;
                while(!letters[k])
                {
                    if(k >= 26)
                        {
                            if(finishHole())
                                getOutput();
                            else
                                return;
                            break;
                        }
                    else
                        k++;
                }
                startNew(toLetter(k));
            }
        }
    }
    // Taking steps
    for(int8_t yStep = -1; yStep <= 1; yStep++)
        for(int8_t xStep = -1; xStep <=1; xStep++)
        {
            if(xStep == 0 && yStep == 0)
                continue;
            if(availability(lt, xNow, yNow, xStep, yStep))
            {
                // Add link
                int i = 0;
                while(links[i][0] != -1)
                    i++;
                links[i][0] = xNow; links[i][1] = yNow;
                links[i][2] = xNow + xStep; links[i][3] = yNow + yStep;

                // Go
                nextStep(lt, xNow + xStep, yNow + yStep, false);

                // Clear link
                memset(links[i], -1, sizeof(links[i]));
            }
        }
}

void startNew(char lt)
{
    //cout<<"New: "<<lt<<endl;
    int x, y;
    bool found = false;
    for(y = 0; y < sizey; y++)
    {
        for(x = 0; x < sizex; x++)
            if(square[x][y] == lt)
                {
                    found = true;
                    break;
                }
        if(found)
            break;
    }
    nextStep(lt, x, y, true);
}

int8_t pointPathSum(int8_t x, int8_t y)
{
    int8_t r = 0;
    for(int i = 0; i < MAXLINK; i++)
        if((links[i][0] == x && links[i][1] == y) || (links[i][2] == x && links[i][3] == y))
            r++;
    return r;
}

bool finishLetter(char lt)
{
    for(int y = 0; y < sizey; y++)
        for(int x = 0; x < sizex; x++)
        {
            //cout<<"Finish Letter: "<<(int)pointPathSum(x, y)<<endl;
            if(square[x][y] == lt && pointPathSum(x, y) < 1)
                return false;
            if(square[x][y] == toSmall(lt) && pointPathSum(x, y) < 2)
                return false;
        }
    return true;
}

bool finishHole()
{
    for(int y = 0; y < sizey; y++)
        for(int x = 0; x < sizex; x++)
        {
            if(square[x][y] >= '0' && square[x][y] <= '8')
                if(pointPathSum(x, y) < toNum(square[x][y]))
                    return false;
        }
    return true;
}

bool availability(char lt, int8_t xNow, int8_t yNow, int8_t xStep, int8_t yStep)
{
    int8_t xDes = xNow + xStep;
    int8_t yDes = yNow + yStep;

    // Out of the image
    if(xDes < 0 || yDes < 0 || xDes >= sizex || yDes >= sizey)
        return false;
    // Color not match
    if(square[xDes][yDes] >= 'A' && square[xDes][yDes] <= 'Z' && square[xDes][yDes] != lt)
        return false;
    if(square[xDes][yDes] >= 'a' && square[xDes][yDes] <= 'z' && square[xDes][yDes] != toSmall(lt))
        return false;
    // Color match but taken
    if(square[xDes][yDes] == toSmall(lt) || square[xDes][yDes] == lt)
    {
        for(int i = 0; i < MAXLINK; i++)
            if((links[i][0] == xDes && links[i][1] == yDes) || (links[i][2] == xDes && links[i][3] == yDes))
                return false;
    }
    // Holes full
    int taken = 0;
    int avail = toNum(square[xDes][yDes]);
    for(int i = 0; i < MAXLINK; i++)
        if((links[i][0] == xDes && links[i][1] == yDes) || (links[i][2] == xDes && links[i][3] == yDes))
            taken++;
    if(taken == avail)
        return false;
    // X-Cross problem
    if(abs(xStep) == 1 && abs(yStep) == 1)
    {
        for(int i = 0; i < MAXLINK; i++)
        {
            if(links[i][0] == xDes && links[i][1] == yNow && links[i][2] == xNow && links[i][3] == yDes)
                return false;
            if(links[i][0] == xNow && links[i][1] == yDes && links[i][2] == xDes && links[i][3] == yNow)
                return false;
        }
    }
    // Path taken
    for(int i = 0; i < MAXLINK; i++)
    {
        if(links[i][0] == xNow && links[i][1] == yNow && links[i][2] == xDes && links[i][3] == yDes)
            return false;
        if(links[i][0] == xDes && links[i][1] == yDes && links[i][2] == xNow && links[i][3] == yNow)
            return false;
    }
    // Available
    return true;
}

void getOutput()
{
    cout<<"Result: "<<endl;

    for(int i = 0; i < MAXLINK; i++)
        if(links[i][0] != -1)
            cout<<"("<<(int)links[i][0]<<","<<(int)links[i][1]<<") TO ("<<(int)links[i][2]<<","<<(int)links[i][3]<<")"<<endl;

    char result[40][40];
    memset(result, ' ', sizeof(result));
    for(int y = 0; y < sizey; y++)
        for(int x = 0; x < sizex; x++)
        {
            result[x * 2][y * 2] = square[x][y];
        }
    for(int i = 0; i < MAXLINK; i++)
    {
        if(links[i][0] != -1)
        {
            if(abs(links[i][0] - links[i][2]) == 1 && links[i][1] == links[i][3])
                result[links[i][0] + links[i][2]][links[i][1] + links[i][3]] = '-';
            if(abs(links[i][1] - links[i][3]) == 1 && links[i][0] == links[i][2])
                result[links[i][0] + links[i][2]][links[i][1] + links[i][3]] = '|';
            if((links[i][0] - links[i][2]) == (links[i][1] - links[i][3]))
                result[links[i][0] + links[i][2]][links[i][1] + links[i][3]] = '\\';
            if((links[i][0] - links[i][2]) + (links[i][1] - links[i][3]) == 0)
                result[links[i][0] + links[i][2]][links[i][1] + links[i][3]] = '/';
        }
    }
    for(int y = 0; y < sizey * 2 - 1; y++)
    {
        for(int x = 0; x < sizex * 2 - 1; x++)
        {
            cout<<result[x][y];
        }
        cout<<endl;
    }

    t_end = clock();
    double totalTime = (double)(t_end - t_start);
    cout<<totalTime<<endl;

    exit(0);
}

int main()
{
    memset(square, '!', sizeof(square));
    memset(links, -1, sizeof(links));
    memset(letters, false, sizeof(letters));

    cout<<"Input the size of the puzzle (x y): ";
    cin>>sizex>>sizey;

    cout<<"Input the puzzle."<<endl;
    cout<<"Use Capital Letters for endpoints and the same Small Letters for the paths;"<<endl;
    cout<<"Use Numbers for the holes."<<endl<<endl;

    for(int y = 0; y < sizey; y++)
        for(int x = 0; x < sizex; x++)
        {
            cin>>square[x][y];
            if(square[x][y] >= 'A' && square[x][y] <= 'Z')
                letters[toSeq(square[x][y])] = true;
            if(square[x][y] >= '1' && square[x][y] <= '4')
                square[x][y] = toNum(square[x][y]) * 2 + '0';
        }

    t_start = clock();

    int8_t k = 0;
    while(!letters[k])
        k++;
    startNew(toLetter(k));

    return 0;
}

Steamコミュニティよりのテストデータ

C-09 3x3
y 2 B Y 3 2 Y b B

F-01 4x4
B b b Y r r R 2 B 3 3 y b b R Y

X-01 3x8
a a a a a a A 2 A a a a 2 3 a 2 3 0 a 3 a a a a

Z-01 4x8
r r r R r 3 2 r r R r r y Y b B 2 3 2 B 2 3 Y b y 2 4 b 0 y y b

Z-02 4x8
Y 2 y y r r 4 y R r y r Y 2 y r B b r 2 b 3 3 b b 3 2 2 R B b 0