#include #include #include #include using namespace std; #define MAX 52 struct Bod { int x; int y; bool operator==(const Bod &b) const { return (x==b.x && y==b.y); } bool operator!=(const Bod &b) const { return (x!=b.x || y!=b.y); } }; struct Poz { Bod bod; int krok; }; int W, H, N; char mapa[MAX][MAX]; int stav[MAX][MAX][MAX*MAX]; Poz back[MAX][MAX][MAX*MAX]; Bod pr[2][MAX]; int D[2]; Bod S, C; Bod smer[5] = {{0, 0}, {1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // Největší společný dělitel int NSD(int a, int b) { if (b==0) return a; else return NSD(b, a%b); } // Nejmenší společný násobek int NSN(int a, int b) { return (a*b)/NSD(a, b); } int main() { freopen("vstup.in", "r", stdin); freopen("vystup.out", "w", stdout); // Načtení vstupu scanf("%d%d%d", &W, &H, &N); for (int y=0; y q; q.push((Poz){S, 0}); stav[S.y][S.x][0] = 0; bool konec = false; int K = -1; while (!q.empty() && !konec) { Poz p = q.front(); q.pop(); int krok = p.krok; Bod akt = p.bod; for (int i=0; i<5; i++) { Bod dalsi = {akt.x+smer[i].x, akt.y+smer[i].y}; if (dalsi.x >= 0 && dalsi.x < W && dalsi.y >=0 && dalsi.y < H && mapa[dalsi.y][dalsi.x]!='#' && stav[dalsi.y][dalsi.x][(krok+1)%MOD]==-1) { if (dalsi==C && dalsi!=pr[0][krok%D[0]] && dalsi!=pr[1][krok%D[1]]) { stav[dalsi.y][dalsi.x][(krok+1)%MOD] = stav[akt.y][akt.x][krok%MOD]+1; back[dalsi.y][dalsi.x][(krok+1)%MOD] = (Poz){akt, krok%MOD}; konec = true; K = krok+1; } else if (dalsi!=pr[0][krok%D[0]] && dalsi!=pr[1][krok%D[1]] && dalsi!=pr[0][(krok+1)%D[0]] && dalsi!=pr[1][(krok+1)%D[1]]) { stav[dalsi.y][dalsi.x][(krok+1)%MOD] = stav[akt.y][akt.x][krok%MOD]+1; back[dalsi.y][dalsi.x][(krok+1)%MOD] = (Poz){akt, krok%MOD}; q.push((Poz){dalsi, krok+1}); } } } } if (!konec) printf("-1\n"); else { stack s; Poz akt = {C, K%MOD}; while (akt.bod!=S || akt.krok!=0) { s.push(akt.bod); akt = back[akt.bod.y][akt.bod.x][akt.krok]; } printf("%d\n", K); while (!s.empty()) { printf("%d %d\n", s.top().x, s.top().y); s.pop(); } } fclose(stdin); fclose(stdout); return 0; }