I manage to solve it in two way:

1.Use two bfs,one forward for change boot(see the adjacent same square as one region)...the other backward for the distance(based on step one,I think it has a bit like DP),and then you can solve it in O(nm).

2.Use dijkstra+heap.Just minimal heap can perform O(vlgv) in this problem(v=nm).Although it is a bit slow than 1,I think it is more simpler......

The interesting place is: In both of the two program(pascal),I only use
  one array[1..500,1..500]of byte,
  three array[1..500,1..500]of longint
it is 3250k,so the total memory won't more than 4000K.but the judge said P1 uses 5513K,P2 uses 4545K.Why will happen this thing?