Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- http://repl.it/erT/1
- local WHITE = nil
- local RED = 0
- local BLACK = 1
- local function visit(M, color, lastcolor, i)
- local pickedcolor = (lastcolor+1) % 2
- if (color[i] == WHITE) then
- color[i] = pickedcolor
- for j = 1, #M do
- if (i ~= j and (M[i][j] == 1 or M[j][i] == 1)) then
- if (not visit(M, color, pickedcolor, j)) then
- return false
- end
- end
- end
- elseif (color[i] ~= pickedcolor) then
- return false
- end
- return true
- end
- local function cantwocolor(M)
- local color = {}
- for i = 1, #M do
- if (color[i] == WHITE) then
- if (not visit(M, color, 0, i)) then
- return false
- end
- end
- end
- return true
- end
- local M1 = {
- {0,1,0,0},
- {0,0,1,0},
- {0,0,0,1},
- {1,0,0,0},
- }
- local M2 = {
- {0,1,0},
- {0,0,1},
- {1,0,0},
- }
- local M3 = {
- {0,1,1,0,0,0},
- {1,0,0,1,0,0},
- {0,0,0,0,0,1},
- {0,0,0,0,0,0},
- {1,0,1,0,0,0},
- {0,0,0,0,0,0},
- }
- local M4 = {
- {0,1,1,0,0,0,0},
- {1,0,0,1,0,0,0},
- {0,0,0,0,0,1,0},
- {0,0,0,0,0,0,0},
- {1,0,0,0,0,0,1},
- {0,0,0,0,0,0,0},
- {0,0,1,0,0,0,0},
- }
- print(cantwocolor(M1), "expected", true)
- print(cantwocolor(M2), "expected", false)
- print(cantwocolor(M3), "expected", false)
- print(cantwocolor(M4), "expected", true)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement