Using a novel differential magneto-optical imaging technique we investigate the phenomenon of vortex lattice melting in crystals of Bi2Sr2CaCu2O8 (BSCCO). The images of melting reveal complex patterns in the formation and evolution of the vortex solid-liquid interface with varying field (H)/temperature (T). We believe that the complex melting patterns are due to a random distribution of material disorder/inhomogeneities across the sample, which create fluctuations in the local melting temperature or field value. To study the fluctuations in the local melting temperature/field, we have constructed maps of the melting landscape Tm(H, r), viz., the melting temperature (Tm) at a given location (r) in the sample at a given field (H). A study of these melting landscapes reveals an unexpected feature: the melting landscape is not fixed, but changes rather dramatically with varying field and temperature along the melting line. It is concluded that the changes in both the scale and shape of the landscape result from the competing contributions of different types of quenched disorder which have opposite effects on the local melting transition.