#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define MAX_SIZE 2000
#define BUFFER_SIZE 2100

typedef struct Point {
    int x;
    int y;
} Point;

typedef struct QueueNode {
    Point p;
    struct QueueNode *next;
} QueueNode;

typedef struct Queue {
    int size;
    QueueNode *head;
    QueueNode *tail;
} Queue;

Point create_point(int x, int y) {
    Point p;
    p.x = x;
    p.y = y;
    return p;
}

QueueNode *create_node(int x, int y) {
    QueueNode* node = (QueueNode *) malloc(sizeof(QueueNode));
    node->p = create_point(x, y);
    node->next = NULL;
    return node;
}

Queue *create_queue() {
    Queue *queue = (Queue *) malloc(sizeof(Queue));
    queue->size = 0;
    queue->head = create_node(0, 0);
    queue->tail = create_node(0, 0);
    queue->head->next = queue->tail;
    return queue;
}

void push(int x, int y, Queue *q) {
    QueueNode* temp = q->head;
    for (int i = 0; i < q->size; i++)
        temp = temp->next;

    QueueNode* node = create_node(x, y);
    node->next = temp->next;
    temp->next = node;

    q->size++;
}

Point pop(Queue *q) {
    QueueNode *temp = q->head->next;
    q->head->next = temp->next;

    Point data = temp->p;

    free(temp);
    q->size--;

    return data;
}

int isEmpty(Queue *q) {
    return q->size == 0;
}

int N, M;

int checkPoint(Point *p) {
    return p->x >= 0 && p->y >= 0 && p->x < N && p->y < M;
}

void printSolution(int L[N][M], Point p) {
    if (p.x == 0 && p.y == 0) {
        return;
    }

    Point points[4] = {
        create_point(p.x, p.y - 1),
        create_point(p.x, p.y + 1),
        create_point(p.x - 1, p.y),
        create_point(p.x + 1, p.y)
    };

    for (int i = 0; i < 4; i++) {
        if (checkPoint(points + i) && L[points[i].x][points[i].y] == L[p.x][p.y] - 1) {
            printSolution(L, points[i]);
            printf("(%d, %d)\n", points[i].x +1, points[i].y + 1);
            return;
        }
    }
}

int main() {
    FILE* file_input = fopen("Labirint.txt", "r");

    printf("Введите N и M: ");
    scanf("%d %d", &N, &M);

    char l[N][M];

    char buffer[BUFFER_SIZE];
    for (int i = 0; i < N; i++) {
        fgets(buffer, BUFFER_SIZE, file_input);
        for (int j = 0; j < M; j++)
            l[i][j] = buffer[j];
    }

    int L[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (l[i][j] == '.') {
                L[i][j] = INT_MAX;
            } else L[i][j] = -1;
        }
    }

    // Инициализация
    Queue* q1 = create_queue();
    Queue* q2 = create_queue();
    L[0][0] = 0;
    push(0, 0, q1);
    int nc = 1;


    // Итерация
    while (!isEmpty(q1)) {

        while (!isEmpty(q1)) {
            Point p = pop(q1);

            Point points[4] = {
                create_point(p.x, p.y - 1),
                create_point(p.x, p.y + 1),
                create_point(p.x - 1, p.y),
                create_point(p.x + 1, p.y)
            };

            for (int i = 0; i < 4; i++) {
                int x = points[i].x;
                int y = points[i].y;
                if (checkPoint(points + i) && L[x][y] >= nc) {
                    L[x][y] = nc;
                    push(x, y, q2);
                }
            }
        }

        Queue *temp = q1;
        q1 = q2;
        q2 = temp;

        nc++;
    }

    // Вывод результата
    if (L[N-1][M-1] == INT_MAX) {
        printf("no solution");
    } else {
        printf("%d\n", L[N-1][M-1]);
        printSolution(L, create_point(N-1, M-1));
        printf("(%d, %d)\n", N, M);
    }

    return 0;
}