If you are not interested in the edges, only painting the sites with different colors, you can use a variation of flood fill starting with the seeds and only stacking the pixel if that color has distance lower than the one already painted that pixel.