View Code of Problem 3852

#include <stdio.h>
#include <string.h>
#define ll long long
#define INF 0x3f3f3f3f 

typedef struct queue {
	int qqq[300];
	int head;
	int tail;
	int empty,full;
} Queue;

Queue qq;
int marked[105][105];
ll map[105][105];
int n,m;
ll L;

int dexx(int row, int col) {
	return (row-1)*m+col;
}
 
void redexx(int dex, int *vi, int *vj) {
	*vj = (dex-1)%m+1;
	*vi = (dex-1)/m+1;
}

void queue_init() {
	qq.head = 1;
	qq.tail = 1;
	qq.empty = 1;
	qq.full = 0;
}

void enque(int x) {
	qq.qqq[qq.tail] = x;
	if(qq.tail<299) {
		qq.tail++;
	} else {
		qq.tail = 0;
	}
	qq.empty = 0;
	if(qq.head==qq.tail+1||(qq.head==0&&qq.tail==299)) {
		qq.full=1;
	}
}
int deque() {
	int x = qq.qqq[qq.head];
	qq.full=0;
	if(qq.head<299) {
		qq.head++;
	} else {
		qq.head = 0;
	}
	if(qq.head==qq.tail) {
		qq.empty=1;
	}
	return x;
}

int bfs() {
	ll x;
	int i,j;
	int get=0;
	int s1,s2,deep;
	memset(marked, 0, sizeof(marked));
	queue_init();
	enque(1);
	deep=0;
	marked[1][1]=1;
	s1=1;
	s2=0;
	while(qq.empty!=1) {
		redexx(deque(),&i,&j);
		s1--;
		if(i!=1&&marked[i-1][j]==0) {
			x = map[i][j]-map[i-1][j]>=0?map[i][j]-map[i-1][j]:map[i-1][j]-map[i][j];
			if(x<=L){
				marked[i-1][j] = 1;
				enque(dexx(i-1,j));
				s2++;
			}
		}
		if(i!=n&&marked[i+1][j]==0) {
			x = map[i][j]-map[i+1][j]>=0?map[i][j]-map[i+1][j]:map[i+1][j]-map[i][j];
			if(x<=L) {
				if(i+1==n&&j==m) {
					deep++;
					return deep;
				}
				marked[i+1][j]=1;
				enque(dexx(i+1,j));
				s2++;
			}
		}
		if(j!=1&&marked[i][j-1]==0) {
			x = map[i][j]-map[i][j-1]>=0?map[i][j]-map[i][j-1]:map[i][j-1]-map[i][j];
			if(x<=L) {
				marked[i][j-1]=1;
				enque(dexx(i,j-1));
				s2++;
			}
		}
		if(j!=m&&marked[i][j+1]==0) {
			x = map[i][j]-map[i][j+1]>=0?map[i][j]-map[i][j+1]:map[i][j+1]-map[i][j];
			if(x<=L) {
				if(i==n&&j+1==m) {
					deep++;
					return deep;
				}
				marked[i][j+1] = 1;
				enque(dexx(i,j+1));
				s2++;
			}	
		}
		if(s1==0) {
			s1 = s2;
			s2 = 0;
			deep++;
		}
	}
	return -1;
}

int main() {
	int T;
	int i,j;
	scanf("%d",&T);
	while(T--) {
		memset(map,0x3f,sizeof(map));
		scanf("%d %d %lld",&n,&m,&L);
		for(i=1;i<=n;i++) {
			for(j=1;j<=m;j++) {
				scanf("%lld",&map[i][j]);
			}
		}
		printf("%d\n",bfs());
	}
}