P4554 小明的游戏

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 ;
}