Cod sursa(job #1698130)

Utilizator mihaisanMihai Sandulescu mihaisan Data 3 mai 2016 19:21:35
Problema Car Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.13 kb
#define _CRT_SECURE_NO_WARNINGS 1

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

#define NMAX 1001
#define N2MAX 1000001

typedef struct queue {
	      int a[N2MAX];
		  int first, last;
        }TQUEUE;

int dx[] = {0 , 1, 0, -1};
int dy[] = {-1, 0, 1, 0};

char b[NMAX][NMAX];
char visit[NMAX][NMAX];
int d[NMAX][NMAX];
TQUEUE q[2];

void init(TQUEUE* q) {
  q->first = 0;
  q->last = -1;
}

int isEmpty(TQUEUE* q) {
  return (q->last + 1 == q->first) ? 1 : 0;
}

void enqueue(TQUEUE* q, int v) {
  q->last++;
  q->a[q->last] = v;
}

int dequeue(TQUEUE* q) {
  int v = q->a[q->first++];
  return v;
}

int encode(int u, int v) {
  return (u << 10) + v;
}

void decode(int v, int* x, int *y) {
  *y = v & 0x01ff;
  *x = (v >> 10) & 0x01ff;
}

void bfs(int n, int m, int pl, int pc, int cl, int cc) {
  int i, l, c, ln, cn;
  int qidx;

  memset(d, 0, sizeof(d));
  memset(visit, 0, sizeof(visit));

  init(&q[0]);
  init(&q[1]);

  enqueue(&q[0], encode(pl, pc));
  d[pl][pc] = 0;
  visit[pl][pc] = 1;

  qidx = 0;
  while (!isEmpty(&q[qidx])) {
	while (!isEmpty(&q[qidx])) {
      decode(dequeue(&q[qidx]), &l, &c);
	  
	  if (visit[l][c] != 1)
		  continue;

      for (i = 0; i < 4; i++) {
        ln = l + dy[i];
	    cn = c + dx[i];

	    if ((1 <= ln) && (ln <= n) && (1 <= cn) && (cn <= m))
	      if ((b[l][c] == b[ln][cn]) && (visit[ln][cn] == 0 || d[ln][cn] > d[l][c])) {
			visit[ln][cn] = 1;
		    d[ln][cn] = d[l][c];
		    enqueue(&q[qidx], encode(ln, cn));
		  }
		  else 
		    if ((b[l][c] != b[ln][cn]) &&  (visit[ln][cn] == 0)) {
			  visit[ln][cn] = 1;
		      d[ln][cn] = d[l][c] + 1;
		      enqueue(&q[1-qidx], encode(ln, cn));
		    }
	  }

	  visit[l][c]++;
    }

	qidx = 1-qidx;
  }
}

int main() {
  int n, m, pl, pc, cl, cc;
  int i, j, v;

  //freopen("padure1.txt", "r", stdin);

  scanf("%d %d %d %d %d %d", &n, &m, &pl, &pc, &cl, &cc);
  for (i = 1; i <= n; i++)
	  for (j = 1; j <= m; j++) {
		  scanf("%d", &v);
		  b[i][j] = (char)v;
	  }

  bfs(n, m, pl, pc, cl, cc);

  printf("%d\n", d[cl][cc]);

  return 0;
}