Submission #11476523

---

Source Code Expand

#include <iostream>

using namespace std;

int r, c;
int sy, sx;
int gy, gx;
int cost[1000][1000];
string map[1000];

typedef struct
{
    int r;
    int c;
} pos;

#define DATA_MAX 100

typedef struct
{
    int pos_first = 0;
    int pos_last = 0;
    pos data[DATA_MAX];
} que;

que q;

void push(que *q, pos data)
{
    if (q->pos_last - q->pos_first >= 100)
    {
        cout << "data overflowed!!!" << endl;
        exit(1);
    }

    q->data[q->pos_last++ % DATA_MAX] = data;
}

pos pop(que *q)
{
    if (q->pos_first == q->pos_last)
    {
        pos ret = {-1, -1};
        return ret;
    }

    return q->data[q->pos_first++ % DATA_MAX];
}

void setNext(int row, int col, int n_cost)
{
    if (row < 0 || row >= r || col < 0 || col >= c)
        return;
    if (map[row][col] == '#')
        return;
    if (n_cost >= cost[row][col])
        return;

    cost[row][col] = n_cost;
    pos n_pos = {row, col};
    push(&q, n_pos);

    return;
}

int main()
{
    cin >> r >> c;
    cin >> sy >> sx;
    cin >> gy >> gx;
  	sy--;sx--;
  	gy--;gx--;

    for (int idx = 0; idx < r; idx++)
    {
        cin >> map[idx];
    }

    for (int idx = 0; idx < r; idx++)
    {
        for (int idx_c = 0; idx_c < c; idx_c++)
        {
            cost[idx][idx_c] = r * c;
        }
    }

    pos start = {sy, sx};
    push(&q, start);
    cost[sy][sx] = 0;

    while (true)
    {
        pos p_now = pop(&q);
        if (p_now.c == -1)
            break;

        int cost_next = cost[p_now.r][p_now.c] + 1;

        setNext(p_now.r - 1, p_now.c, cost_next);
        setNext(p_now.r + 1, p_now.c, cost_next);
        setNext(p_now.r, p_now.c - 1, cost_next);
        setNext(p_now.r, p_now.c + 1, cost_next);
    }

  /*
    for (int idx = 0; idx < r; idx++)
    {
        for (int idx_c = 0; idx_c < c; idx_c++)
        {
            if (map[idx][idx_c] == '#')
            {
                printf("#");
            }
            else
            {
                printf("%d", cost[idx][idx_c]);
            }
        }
        printf("\n");
    }
*/
    cout << cost[gy][gx] << endl;

    return 0;
}

Submission Info

Judge Result