Five Character ASCII Map

Question

Note: In this post, the terms 'character' and 'color' mean essentially the same thing

This image:

can be represented as

....'''333
.eeee'''3e
..dddd33ee
%%%dd####e

(mapping colors to ascii characters)

The four color theorem states that "given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions." - Wikipedia (link)

This means that it should be possible to color a map using four colors so that no two parts which share an edge share a color.

The algorithm to color a map using only four colors is complicated so in this challenge your program only needs to color the map using five or less colors.

The previous map recolored could look like this:

which could be represented as

....'''333
.eeee'''3e
..dddd33ee
333dd....e

or equivalently

@@@@$$$!!!
@^^^^$$$!^
@@<<<<!!^^
!!!<<@@@@^

Challenge:

Given a "map" made of ascii characters (where each character represents a different color), "recolor" the map (represent the map using different ascii characters) so that it only uses five or less colors.

Example:

Input:

%%%%%%%%%%%%##########$$$$$$$$%%
*****%%%####!!!!!!!%%%%%%%%%#^^^
(((((((***>>>>??????????%%%%%%%%
&&&&&&&&$$$$$$$^^^^^^^))@@@%%%%%
^^^^^^%%%%%%%%%%%%##############

Possible output:

11111111111122222222223333333311
44444111222255555551111111112444
22222224441111444444444411111111
55555555222222255555553355511111
22222211111111111122222222222222

Clarifications:

• The input map will always use six or more characters
• You may use any five different characters in the output
• You can use less than different five characters in the output
• You may take the input in any reasonable format (including an array of arrays, or an array of strings)
• This is code-golf so the shortest answer wins.

Sandbox link

Answer 1

Python 2, 375 361 359 357 355 353 350 347 bytes

e=enumerate
C=set('12345')
def f(s):
 s=[map(ord,l)for l in s]
 for i,v in e(s):
	for j,w in e(v):
	 if{w}-C:
		F,N=g([],s,i,j,w)
		for y,x in F:s[y][x]=min(C-N)
 return s
def g(m,s,i,j,c):
 n={s[i][j]}
 if(n^{c}or(i,j)in m)<1:
	m+=(i,j),
	for x,y in(0,1),(0,-1),(1,0),(-1,0):
	 if len(s)>i+x>-1<j+y<len(s[0]):m,N=g(m,s,i+x,j+y,c);n|=N
 return m,n

Try it online!

Takes input as a list of strings, and returns a list of lists

f takes the map input and colors it, g returns all connected characters and the set of their neighbors, to the area can be colored with a distinct color.