[Queue(BFS)] 댐/dam

Question

30 계단 > 큐 > 댐(dam)

Solving

Code

[#M_더보기|접기|

#include <iostream>
using namespace std;
 
typedef struct position
{
    int posX;
    int posY;
    int order;
}pos;
 
int t, map[103][103], sX, sY, k;
pos queue[10000], tmp;
int front, rear, cnt, key;
 
int dirx[] = { -1, 0, 1, 0 };
int diry[] = { 0, -1, 0, 1 };
 
void enqueue(int xx, int yy, int zorder)
{
    queue[rear].posX = xx;
    queue[rear].posY = yy;
    queue[rear].order = zorder;
    map[yy][xx] = zorder;
    rear++;
}
 
int isempty()
{
    if (rear - front == 0)
        return 1;
    return 0;
}
 
pos dequeue()
{    
    if (isempty())
    {
        key = 1;
        cout << "OH, MY GOD" << endl;        
    }    
    return queue[front++];
}
 
int main()
{
    cin >> t;
    for (int y = 0; y <= t+1; y++)
        for (int x = 0; x <= t+1; x++)
            map[y][x] = -1;
 
    for (int y =1 ; y <= t; y++)
        for (int x = 1; x <= t; x++)
        {
            cin >> map[y][x];
            if (map[y][x])
                map[y][x] = -1;
        }
 
    cin >> sX >> sY;
    cin >> k;
 
    enqueue(sX, sY, cnt);
        
    while (1)
    {    
        tmp = dequeue();
        int cnt_t = 0;
 
        if (key)
            break;
 
        cnt = tmp.order + 1;
        for (int i = 0; i < 4; i++)
            if (!(tmp.posY + diry[i] == sY && tmp.posX + dirx[i] == sX))
                if (map[tmp.posY + diry[i]][tmp.posX + dirx[i]] == 0)
                    enqueue(tmp.posX + dirx[i], tmp.posY + diry[i], cnt);
 
        if (k < cnt)
        {
            for (int y = 1; y <= t; y++)
                for (int x = 1; x <= t; x++)
                    if (map[y][x] == k)
                        cnt_t++;
            cout << cnt_t << endl;
            break;
        }        
    }
    return 0;
}

_M#]