Colorarea Hărților

Problemă:

Se dă harta administrativă a unei ţări, în care sunt puse în evidenţă judeţele (în număr de n). Se pune problema colorării judeţelor, astfel încât, dacă două judeţe sunt vecine, ele să aibe culori diferite. Sunt disponibile m culori distincte.

Implementare:

Cod Sursa VB

 

Module Module1
Dim x(100) As Integer
Dim n, m, k As Integer
Dim NrSol As Integer
Dim buna As Boolean
Dim v(100, 100) As Boolean

    Function EsteBuna(ByVal k As Integer) As Boolean
Dim i As Integer
Dim atac As Boolean
atac = False
i = 1
While (i < k And Not atac)
If (x(i) = x(k) And v(i, k) = True) Then
atac = True
Else
i = i + 1
End If
End While
Return Not atac
End Function

    Sub ScrieSolutia()
Dim i As Integer
Console.WriteLine(“Solutia numarul ” & NrSol & “: “)
For i = 1 To n Step 1
Console.WriteLine(” Tara nr. ” & i & ” se coloreaza in culoarea ” & x(i))
Next i
End Sub

    Sub Main()
Dim i, j As Integer
Console.WriteLine(“Problema colorarii hartilor”)
Console.Write(“Dati numarul de culori “)
m = Convert.ToInt32(Console.ReadLine())
Console.Write(“Dati numarul de tari “)
n = Convert.ToInt32(Console.ReadLine())
For i = 1 To n
v(i, i) = 0
Next i
For i = 1 To n – 1
For j = i + 1 To n
Console.Write(“Este tara ” & i & ” vecina cu tara ” & j & “?Da=1, Nu=0 “)
v(i, j) = Convert.ToString(Console.ReadLine())
v(j, i) = v(i, j)
Next j
Next i
k = 1
x(k) = 0
While k > 0
buna = False
While (x(k) < m And Not buna)
x(k) = x(k) + 1
If (EsteBuna(k)) Then
buna = True
End If
End While
If (buna) Then
If (k = n) Then
NrSol = NrSol + 1
ScrieSolutia()
Else
k = k + 1
x(k) = 0
End If
Else
k = k – 1
End If
End While
Console.WriteLine(“Total: ” & NrSol & ” solutii.”)
Console.ReadLine()
End Sub

End Module

Cod Sursa C++

#include “stdafx.h”
#include <iostream>
#include <conio.h>

using namespace std;

int x[100];
int n;
int m;
int k;
int NrSol;
bool buna;
bool v[100][100];

bool EsteBuna(int k)
{
int i;
bool atac;
atac=false; i=1;
while(i<k && !atac)
{
if(x[i]==x[k] && v[i][k]==1)
atac=true;
else
i++;
}
return !atac;
}

void ScrieSolutia()
{
int i;
cout<<“Solutia numarul “<<NrSol<<“: “<<endl;
for (i=1;i<=n;i++)
cout<<” Tara nr. “<<i<<” se coloreaza in culoarea “<<x[i]<<endl;
cout<<endl;
}

int main()
{
int i,j;
cout<<“Problema colorarii hartii “<<endl;
cout<<“Dati numarul de culori: “; cin>>m;
cout<<“Dati numarul de tari: “; cin>>n;
for (i=1;i<=n;i++)
v[i][i]=0;
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
{
cout<<“Este tara “<<i<<” vecina cu tara “<<j<<” Da=1; Nu=0 “;
cin>>v[i][j];
v[j][i]=v[i][j];
}
k=1; x[k]=0;
while(k>0)
{
buna = 0;
while(x[k]<m && !buna)
{
x[k]=x[k]+1;
if (EsteBuna(k))
buna = 1;
}
if (buna)
if (k==n)
{
NrSol++;
ScrieSolutia();
}
else
{
k++;
x[k]=0;
}
else
k=k-1;
}
cout<<“Total: “<<NrSol<<” solutii.”<<endl;
system(“pause”);
}

Cod Sursa PASCAL

program ProblemaColorariiHartii;
var x: array[1..100] of Integer; { vector pentru memorarea solutiilor }
n: Integer; { numarul de tari } NrSol: Integer; { numarul de solutii }
m: Integer; { numarul de culori disponibile }
k: Integer; { tara curenta }
buna: Boolean;
{ variabila logica ce indica dasa varianta aleasa pt. tara k
este sau nu buna }
V: array[1..100,1..100] of 0..1; { matricea cu vecinatatile }

function EsteBuna(k: Integer): Boolean;
{ aceasta functie verifica daca tara k este bine colorata,
adica nu are aceeasi culoare cu tarile de pana la ea: 1,2,…, k-1,
vecine cu ea}
var i: Integer; atac: Boolean;
begin
atac:=False; i:=1;
while (i<k) and (not atac) do
if (x[i]=x[k]) and (V[i,k]=1) then
atac:=True
else
i:=i+1;
EsteBuna:=not atac
end;

procedure ScrieSolutia;
{ aceasta procedura afiseaza o solutie gasita }
var i: Integer;
begin
WriteLn(‘Solutia numarul ‘,NrSol,’:’);
for i:=1 to n do
WriteLn(‘  Tara nr. ‘,i,’ se coloreaza in culoarea ‘,x[i]);
WriteLn;
end;

var i,j: Integer;

begin
WriteLn(‘Problema colorarii hartii’);
Write(‘Dati nr. de culori: ‘); ReadLn(m);
Write(‘Dati nr. de tari: ‘); ReadLn(n);
{ punem 0 pe diagonala principala a matricei de vecinatati }
for i:=1 to n do
V[i,i]:=0;
{ citim vecinatatile – matricea de adiacenta V }
for i:=1 to n-1 do
for j:=i+1 to n do
begin
Write(‘Este tara ‘,i,’ vecina cu tara ‘,j,’? DA=1, NU=0: ‘);
ReadLn(V[i,j]);
V[j,i]:=V[i,j]
end;
k:=1; x[k]:=0; { plecam cu prima tara, ii dam culoarea 0 }
while k>0 do
begin
buna:=False;
{ ii dam tarii k urmatoarea culoare, cat timp mai avem culori
si nu am gasit inca o varianta buna }
while (x[k]<m) and (not buna) do
begin
x[k]:=x[k]+1; { dau tarii k urmatoarea culoare }
if EsteBuna(k) then buna:=True { testam culoarea daca e buna }
end;
if buna then { daca am gasit o varianta buna atunci… }
if k=n then { daca am ajuns la ultima tara, afisam solutia }
begin
NrSol:=NrSol+1;
ScrieSolutia
end
else
begin { altfel trecem la urmatoarea tara }
k:=k+1;
x[k]:=0 { si ii dam culoarea 0 }
end
else
k:=k-1; { daca nu am gasit o varianta buna,
ne intoarcem la tara anterioara }
end;
WriteLn(‘Total: ‘,NrSol,’ solutii.’);
ReadLn
end.