var
n, m, i, j, tz : integer;
xi, yi, xe, ye : integer;
a: array [1..100,1..100] of integer;
procedure tipara();
var i, j :integer;
begin
for i:=1 to n do
begin
for j:= 1 to m do write(a[i,j]:3);
writeln;
end;
writeln('-----------------------');
end;
procedure back (x, y, k : integer);
begin
// verificam daca miscarea este legala
// tipara();
if (x < 1 )or (x > n )or (y < 1) or( y > m) then exit;
if (a[x,y] <> 0) then exit;
a[x,y] := k;
if (x = xe )and (y = ye) then begin tipara(); a[x,y] := 0; exit; end;
// miscarile inainte
back(x+1,y, k+1);
back(x-1,y, k+1);
back(x,y+1, k+1);
back(x,y-1, k+1);
// miscarea inapoi
a[x,y] := 0;
end;
begin
// citire date
readln(n, m);
for i := 1 to n do
for j :=1 to m do
begin
read(a[i,j]);
if (a[i,j] = 2) then begin xi := i; yi := j; a[i,j] := 0; end;
if (a[i,j] = 3) then begin xe := i; ye := j; a[i,j] := 0; end;
end;
// verificare
tipara();
back(xi,yi,1);
end.
11 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 -1 0 -1 -1 -1
-1 0 -1 -1 -1 -1 0 0 0 -1
-1 0 0 0 0 0 0 -1 0 -1
-1 -1 0 -1 -1 -1 0 -1 0 3
-1 0 0 0 0 -1 0 -1 -1 -1
-1 0 -1 0 0 0 0 0 0 -1
-1 0 0 0 -1 -1 -1 -1 0 -1
-1 0 -1 0 0 0 0 -1 0 -1
-1 0 -1 0 0 -1 0 0 0 -1
-1 -1 -1 -1 2 -1 -1 -1 -1 -1
var
n, i, j : integer;
x, y: integer;
a: array [1..100,1..100] of integer;
procedure tipara();
var i, j :integer;
begin
for i:=1 to n do
begin
for j:= 1 to n do write(a[i,j]:3);
writeln;
end;
writeln('-----------------------');
end;
procedure back (x, y, k : integer);
begin
// verificam daca miscarea este legala
// tipara();
if (x < 1 )or (x > n )or (y < 1) or( y > n) then exit;
if (a[x,y] <> 0) then exit;
a[x,y] := k;
if (k = n * n) then begin tipara(); a[x,y] := 0; exit; end;
// miscarile inainte
back(x+1,y-2, k+1);
back(x+1,y+2, k+1);
back(x-1,y-2, k+1);
back(x-1,y+2, k+1);
back(x-2,y-1, k+1);
back(x-2,y+1, k+1);
back(x+2,y-1, k+1);
back(x+2,y+1, k+1);
// miscarea inapoi
a[x,y] := 0;
end;
begin
// citire date
readln(n);
read(x,y);
// rezolvare
back(x,y,1);
end.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector <int> adj[20];
int n, m, x, y, b[20], sol[20], s;
int vecini(int x, int y)
{
int flag = 0;
for (int i = 0; i< adj[x].size(); i++) if (adj[x][i] == y) flag = 1;
return flag;
}
void printx(int n)
{
for (int i = 1; i <= n; i++)
cout << sol[i]<<" ";
cout << endl;
}
void sales(int node, int pos) // node - active node, pos - index in route
{
if (b[node]) return;
sol[pos] = node; b[node] = 1;
if (pos == n && vecini (s, node))
{
printx(pos);
b[node] = 0;
return;
}
for (int i = 0; i < adj[node].size(); i++)
sales(adj[node][i], pos + 1);
b[node] = 0;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
// print adjacency list:
/* for (int i = 1; i <= n; i++)
{
for (int j = 0; j < adj[i].size(); j++) cout << adj[i][j] << " ";
cout << endl;
}*/
// find salesman route
s = 1;
sales(s, 1);
return 0;
}
------------------------------------
12 20
2 7
2 1
1 7
1 4
2 3
3 4
4 6
4 5
3 5
5 6
5 8
5 11
10 12
10 11
11 12
12 8
7 8
8 9
7 9
6 7
#include <iostream>
using namespace std;
int a[100][100], q[100], s[100], n;
void fillc(int *x, int z, int num) // umplere tablou X cu valori Z
{
for (int i = 1; i <= num; i++) x[i] = z;
}
void readdata()
{
cin >> n; // citire dimensiune graf
for (int i = 1; i <= n; i++) // citire elemente graf
for (int j = 1; j <= n; j++) cin >> a[i][j] ;
}
void print(int *s, int n) // afisare tablou
{
for (int i = 1; i <= n; i++) if (s[i] == 1) cout << i <<" ";
cout << endl;
}
void m_ind_opt()
{
int k = 0, r, j, rest[100];
for (int i = 1; i <= n; i++) if(q[i]) { k = 1; break;} // verificare posibilitate extindere
if (!k) print(s, n); // nu putem extinde, tipar solutie
else // extindere solutie
{
j = n;
while (j >= 1 && !s[j] ) j--; // cautam ultimul nod adaugat
for (int i = j + 1; i <= n; i++) // cautam noduri pentru adaugare
if (q[i]) // daca am gasit un nod
{
fillc(rest, 0, n);
s[i] = 1; // punem nodul in S
q[i] = 0; // excludem nodul din Q+
for (int h = 1; h <= n; h++) // excludem din Q+ vecinii nodului adaugat
if (a[i][h] && q[h])
{
q[h] = 0; rest[h] = 1;
}
m_ind_opt(); // apelam recursiv
s[i] = 0; // excludem nodul din S
q[i] = 1; // punem nodul in Q
for (int h = 1; h <= n; h++) if(rest[h]) q[h] = 1; // punem vecinii nodului in Q
}
}
}
int main()
{
readdata();
fillc(s,0,n);
fillc(q,1,n);
m_ind_opt();
return 0;
}
-------------------------------------
Sample
8
0 1 0 1 1 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 1
1 0 0 0 1 0 0 0
1 1 0 1 0 0 1 1
0 0 1 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 1 0 1 1 0 0