[게임알고리즘] 8강 재귀와 반복

 

 

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//#define xprintf printf
#define xprintf //printf
 
struct Rect
{
    int x, y, width, height;
};
 
Rect RectMake(int x, int y, int width, int height)
{
    Rect r;
    r.x = x;
    r.y = y;
    r.width = width;
    r.height = height;
    return r;
}
 
typedef unsigned char uint8;
Rect common(int* array, int wNum, int hNum, uint8* visit);
 
 
Rect click(int* array, int wNum, int hNum, int x, int y)
{
    int whNum = wNum * hNum;
    uint8* visit = (uint8*)calloc(sizeof(uint8), whNum);
    visit[wNum * y + x] = 1;
    return common(array, wNum, hNum, visit);
}
 
Rect drag(int* array, int wNum, int hNum, Rect rt)
{
    int whNum = wNum * hNum;
    uint8* visit = (uint8*)calloc(sizeof(uint8), whNum);
    for(int i=rt.x; i<rt.x+rt.width; i++)
    {
        for(int j = rt.y; j<rt.y+rt.height; j++)
            visit[wNum * j + i] = 1;
    }
    return common(array, wNum, hNum, visit);
}
 
Rect common(int* array, int wNum, int hNum, uint8* visit)
{
    while(1)
    {
        bool exist = false;
        for(int j=0; j<hNum; j++)
        {
            for(int i=0; i<wNum; i++)
            {
                int n = wNum * j + i;
                if( visit[n]==1 )
                {
                    visit[n] = 2;
                    xprintf("visit(%d, %d)\n", i, j);
#define canVisit(n) array[n] && visit[n]==0
                    if( i>0 && canVisit(n-1) ) visit[n-1] = 1;
                    if( i<wNum-1 && canVisit(n+1) ) visit[n+1] = 1;
                    if( j>0 && canVisit(n-wNum) ) visit[n-wNum] = 1;
                    if( j<hNum-1 && canVisit(n+wNum) ) visit[n+wNum] = 1;
#undef canVisit
                    exist = true;
                }
            }
        }
        if( exist==false )
            break;
    }
 
    int left;
    for(int i=0; i<wNum; i++)
    {
        bool exist = false;
        for(int j=0; j<hNum; j++)
        {
            if( visit[wNum * j + i] )
            {
                left = i;
                xprintf("found left = %d\n", i);
                exist = true;
                break;
            }
        }
        if( exist )
            break;
    }
    int right;
    for(int i=wNum-1; i>-1; i--)
    {
        bool exist = false;
        for(int j=0; j<hNum; j++)
        {
            if( visit[wNum * j + i] )
            {
                right = i;
                xprintf("found right = %d\n", i);
                exist = true;
                break;
            }
        }
        if( exist )
            break;
    }
    int top;
    for(int j=0; j<hNum; j++)
    {
        bool exist = false;
        for(int i=0; i<wNum; i++)
        {
            if( visit[wNum * j + i] )
            {
                top = j;
                xprintf("found top = %d\n", j);
                exist = true;
                break;
            }
        }
        if( exist )
            break;
    }
    int bottom;
    for(int j=hNum-1; j>-1; j--)
    {
        bool exist = false;
        for(int i=0; i<wNum; i++)
        {
            if( visit[wNum * j + i] )
            {
                bottom = j;
                xprintf("found bottom = %d\n", j);
                exist = true;
                break;
            }
        }
        if( exist )
            break;
    }
 
    xprintf("(%d, %d, %d, %d\n)\n", left, right, top, bottom);
    Rect result = RectMake(left, top, right-left+1, bottom-top+1);
 
    free(visit);
 
    return result;
}
 
int main() {
    int a[10][7] = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
        0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 
        0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 
        0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 
        0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 
        0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    };
    int* p = (int*)a;
    Rect rt[] = {
        click((int*)a, 10, 7, 21 / 20, 31 / 20),
        click((int*)a, 10, 7, 110 / 20, 44 / 20),
        drag((int*)a, 10, 7, 
                    RectMake(42 / 20, 24 / 20, 60 / 20, 40 / 20))
    };
    for(int i=0; i<3; i++)
    {
        Rect* r = &rt[i];
        printf("rt[%d](%d, %d, %d, %d)\n", 
            i, r->x, r->y, r->width, r->height);
    }
 
    return 0;
}
 

 

 

로또
1~45 숫자 중에 6개를 뽑습니다.
이번주 당첨번호 1, 2, 3, 4, 5, 6인데,
1. 몇번만에 1등 당첨번호 나오는지 구하기
2. 행운번호 7번인데, 그 사이 2등 몇번 당첨?
3. 3번을 제외한 번호 6개 중에 3등 몇번 당첨?

#include <iostream>
 
#if 0
#include <stdlib.h>
#include <time.h>
 
// 다르다면 count++
// 같다면 출력 count
void sort(int* n, int num)
{
    int nn = num -1;
    for(int i=0; i<nn; i++)
    {
        for(int j=1+i; j<num; j++)
        {
            if(n[i] < n[j])
            {
                int t = n[i];
                n[i] = n[j];
                n[j] = t;
            }
        }
    }
}
 
int lotto(int* answer)
{
    // answer 오름차(내림)순 정렬
    sort(answer, 6);
 
    int count = 0;
    int t[6];
    while(1)
    {
        bool equal;
        // 1~45 숫자 중에 6개를 뽑습니다.
        for(int i=0; i<6; i++)
        {
            while(1)
            {
                int r = 1 + rand()%45;
                bool exist = false;
                for(int j=0; j<i; j++)
                {
                    if( r==t[j] )
                    {
                        exist = true;
                        break;
                    }
                }
                if( exist==false )
                {
                    t[i] = r;
                    break;
                }
            }
        }
 
        // 뽑은 숫자 오른차(내림)순 정렬
        sort(t, 6);
 
        // 값을 비교 
        equal = true;
        for(int i=0; i<6; i++)
        {
            if( t[i]!=answer[i] )
            {
                equal = false;
                break;
            }
        }
 
        count++;
        if( equal )
            break;
    }
    return count;
}
#else
#include <string.h>
 
int lotto(int* answer)
{
    int count = 0, count2 = 0, count3 = 0;
    bool t[45];
    while(1)
    {
        memset(t, 0x00, 45);
        for(int i=0; i<6; i++)
        {
            while(1)
            {
                int r = rand()%45;
                if( t[r]==false )
                {
                    t[r] = true;
                    break;
                }
            }
        }
 
        int num = 0;
        for(int i=0; i<6; i++)
        {
            if( t[ answer[i]-1 ] )
                num++;
        }
 
        count++;
        if( num==6 )
            break;
        else if(num==5)
        {
            if(t[6])
                count2++;
            else if(t[2]==false)
                count3++;
 
        }
    }
    return count;
}
#endif
 
int main() {
    srand(time(NULL));
 
    int a[] = {1, 2, 3, 4, 5, 6};
    std::cout << lotto(a);
 
    return 0;
}