#include <stdio.h>
#define MAX_N 100
#define MAX_M (MAX_N*MAX_N)
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define abs(a)   (((a) > 0) ? (a) : -(a))
enum {ROW,COL};

struct krizovatka {
  int x,y;
};

struct krizovatka cnn;
struct krizovatka stavky[MAX_M];  //pole se stávkami
int delky[MAX_M][2][MAX_N+1];  //délky do řádku a sloupce jdoucí skrz stávku
int M,N;

int main(void) {
  int i,stavka;
  struct krizovatka m;
  int m_delka;

  printf("Zadejte N a M:");
  scanf("%d %d",&N,&M);
  printf("Zadejte souřadnice CNN:");
  scanf("%d %d",&cnn.x,&cnn.y);

  for (i=0;i<M;i++) {
    printf("Zadejte souřadnice %d. stávky:",i+1);
    scanf("%d %d",&stavky[i].x,&stavky[i].y);
  }

  for (i=1;i<=N;i++) { //počáteční nastavení délky cest do CNN
    delky[M-1][ROW][i]=abs(i-cnn.x)+abs(stavky[M-1].y-cnn.y);
    delky[M-1][COL][i]=abs(stavky[M-1].x-cnn.x)+abs(i-cnn.y);
  }

  for (stavka=M-2;stavka>=0;stavka--) { //pro všechny stávky
    for (i=1;i<=N;i++) {
      delky[stavka][ROW][i]=min(abs(stavky[stavka].y-stavky[stavka+1].y)+delky[stavka+1][ROW][i],
				abs(i-stavky[stavka+1].x)+delky[stavka+1][COL][stavky[stavka].y]);
      delky[stavka][COL][i]=min(abs(stavky[stavka].x-stavky[stavka+1].x)+delky[stavka+1][COL][i],
				abs(i-stavky[stavka+1].y)+delky[stavka+1][ROW][stavky[stavka].x]);
    }
  }
  printf("CNN->"); //výpis trasy
  m=cnn;
  m_delka=min(abs(cnn.y-stavky[0].y)+delky[0][ROW][cnn.x],
	      abs(cnn.x-stavky[0].x)+delky[0][COL][cnn.y]);
  for (stavka=0;stavka<M;stavka++) {
    if (delky[stavka][ROW][m.x]+abs(m.y-stavky[stavka].y) == m_delka) m.y=stavky[stavka].y;
    else m.x=stavky[stavka].x;
    printf("(%d,%d)->",m.x,m.y);
  }
  printf("CNN\n");
  return 0;
}