SPFA板子题

#include <stdio.h>

#include <string.h>

#define Clean(X,K) memset(X,K,sizeof(X))

#define re register

#define GC getchar()

#define Jud(X,Y) (X<0||X>=N||Y<0||Y>=M)

int Qread () {

	int X = 0 ;	char C = GC ;

	while (C > '9' || C < '0') C = GC ;

	while (C >='0' && C <='9') {

		X = X * 10 + C - '0' ;

		C = GC ;

	}

	return X ;

}

const int Maxn = 505 ,INF = 20021020 << 2 , U = 500 * 500 + 5;

int N , M , Mdis[Maxn][Maxn] , Vis[Maxn][Maxn] , Qx[Maxn * Maxn] , Qy[Maxn * Maxn] , Head , Tail ;

const short int Dx[] = {-1,1,0,0} , Dy[] = {0,0,-1,1} ;

char A[Maxn][Maxn] ;

int SPFA (int Sx , int Sy , int Ex , int Ey) {

	Clean (Mdis , 0x3f) , Clean(Vis , 0) , Head = Tail = 1 ;

	Mdis[Sx][Sy] = 0 , Vis[Sx][Sy] = 1 ;

	if (++ Tail > U) Tail = 0 ;

	Qx[Tail] = Sx , Qy[Tail] = Sy ;

	while (Head != Tail) {

		if (++ Head > U) Head = 0 ;

		int Nx = Qx[Head] , Ny = Qy[Head] ;

		Vis[Nx][Ny] = 0 ;

		for (re int i = 0 ; i < 4 ; ++ i) {

			int Tx = Nx + Dx[i] , Ty = Ny + Dy[i] ;

			if (Jud(Tx , Ty)) continue ;

			int Dis = Mdis[Nx][Ny] + (A[Tx][Ty] == A[Nx][Ny] ? 0 : 1) ;

			if (Dis < Mdis[Tx][Ty]) {

				Mdis[Tx][Ty] = Dis ;

				if (!Vis[Tx][Ty]) {

					Vis[Tx][Ty] = 1 ;

					if (++ Tail > U) Tail = 0 ;

					Qx[Tail] = Tx , Qy[Tail] = Ty ;

				}

			}

		}

	}

	return Mdis[Ex][Ey] ;

}

int main () {

//	freopen ("P4554.in" , "r" , stdin) ;

	N = Qread () , M = Qread () ;

	while (N + M) {

		for (re int i = 0 ; i < N; ++ i) for (re int j = 0 ; j < M; ++ j) {

				char C = GC ;

				while (C != '#' && C != '@') C = GC ;

				A[i][j] = C ;

			}

		int Sx = Qread () , Sy = Qread () , Ex = Qread () , Ey = Qread ();

		printf ("%d\n" , SPFA (Sx , Sy , Ex , Ey)) ;

		N = Qread () , M = Qread () ;

	}

	fclose (stdin) , fclose (stdout) ;

	return 0 ;

}