3. zadatak, Križaljka, 110 bodova

Opis algoritma i rješenja u oba programska jezika napisao Jurko Gospodnetić.

Opis algoritma

Nakon unosa podataka program ih postavi u pravilan redosljed te u rekurzivnoj proceduri pokušava sastaviti ispravnu križaljku. To radi na taj način da na svakoj dubini rekurzije pokušava ubaciti riječ na mjestu u križaljci iza posljednje ubačene (od gornjeg lijevog kuta horizontalno po redovima sve do doljnjeg desnog kuta). Za svaku riječ koju proba ubaciti horizontalno provjerava da li je poštivajući dosada poznata slova u križaljci moguće u nju postaviti vertikalne riječi. Ako to nije moguće onda riječ koja se trenutno isprobava ne odgovara na ovom mjestu, a ako se ustanovi da niti jedna riječ iz rječnika ne odgovara na određenom mjestu rekurzija se vraća jedan korak da bi promijenila neke od prije ubačenih riječi. Ako niti jedna riječ ne odgovara na prvom mjestu (1, 1) križaljku nije moguće složiti dok u slučaju da se ispravno popuni mjesto (5, 5) nađena je ispravno popunjena križaljka.

KRIZ.C

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define INPUT_F   "kriz.in"
#define OUTPUT_F  "kriz.out"

#define NOT_USED  '-'
#define CRNO      '*'

typedef char kriz_type[5][5];
typedef char data_type[51][6];

kriz_type kriz;
data_type data;
int       dn;

void unesi_podatke(void)
{
	FILE    *ff;
	int   i, j;
	char  t[6];

	ff = fopen(INPUT_F, "rt");
	strcpy(data[0], "12345");
	fscanf(ff, "%d", &dn);
	for (i = 1; i <= dn; i++)
		fscanf(ff, "%s", data[i]);
	fclose(ff);

	for (i = 1; i < dn; i++)
		for (j = i + 1; j <= dn; j++)
			if (strcmp(data[i], data[j]) > 0) {
				strcpy(t, data[i]);
				strcpy(data[i], data[j]);
				strcpy(data[j], t);
			}
}

void ispisi_rezultat(kriz_type kriz)
{
	FILE    *ff;
	int     i, j;

	ff = fopen(OUTPUT_F, "wt");
	fprintf(ff, "1\n");
	for (j = 0; j < 5; j++) {
		for (i = 0; i < 5; i++)
			fprintf(ff, "%c ", kriz[j][i]);
		fprintf(ff, "\n");
	}
	fclose(ff);
	exit(0);
}

void ispisi_ne(void)
{
	FILE *ff;

	ff = fopen(OUTPUT_F, "wt");
	fprintf(ff, "0\n");
	fclose(ff);
}

char *vert(kriz_type kriz, int x, int y)
{
	int  i, top;
	char res[6];

	top = y - 1;
	while ((top > -1) && (kriz[top][x] != CRNO))
		top--;
	for (i = top + 1; i <= y; i++)
		res[i - top - 1] = kriz[i][x];
	res[y - top] = '\0';
	return strdup(res);
}

int exact_data(data_type data, int dn, char what[6], int except)
{
	int i;
	for (i = 1; i <= dn; i++) {
		if (i == except) continue;
		if (!strcmp(data[i], what))
			return i;
	}
	return 0;
}

int apropos_data(data_type data, int dn, char what[6], int except)
{
	int i;
	for (i = 1; i <= dn; i++) {
		if (i == except) continue;
		if (!strncmp(data[i], what, strlen(what)))
			return i;
	}
	return 0;
}

void copy_data(data_type data1, int dn1, data_type data2, int *dn2, int except)
{
	int i;
	*dn2 = -1;
	for (i = 0; i <= dn1; i++) {
		if (i == except) continue;
		strcpy(data2[++(*dn2)], data1[i]);
	}
}

int ubaci(kriz_type kriz, data_type data, int *dn, int k, int *x, int *y)
{
	int        i, l;
	char       *abc;
	const int  len = strlen(data[k]);

	if (*x + len > 5)
		return 0;
		
	for (i = 0; i < len; i++) {
		if (*y && (kriz[*y - 1][*x + i] != CRNO)) {
			abc = vert(kriz, *x + i, *y - 1);
			abc[strlen(abc) + 1] = '\0';
			abc[strlen(abc)] = data[k][i];
		} else {
			abc = (char *) malloc(2);
			*abc = data[k][i];
			abc[1] = '\0';
		}
		if (*y == 4)
			l = exact_data(data, *dn, abc, k);
		else
			l = apropos_data(data, *dn, abc, k);
		free(abc);
		
		if (!l)
			return 0;
	}
	if (*y && (*x + len < 5)) {
		if (kriz[*y - 1][*x + len] == CRNO)
			return 0;
		abc = vert(kriz, *x + len, *y - 1);
		l = exact_data(data, *dn, abc, k);
		free(abc);

		if (!l)
			return 0;

		copy_data(data, *dn, data, dn, l);
		if (l < k)
			k--;
	}

	for (i = 0; i < len; i++)
		kriz[*y][*x + i] = data[k][i];

	*x += len;
	if (*x < 5)
		kriz[*y][(*x)++] = CRNO;
	if (*x > 4) {
		*x = 0;
		(*y)++;
	}
	
	copy_data(data, *dn, data, dn, k);

	return 1;
}

void do_the_mega_loop(kriz_type kriz, data_type data, int dn, int x, int y)
{
	kriz_type  krizb;
	data_type  datab;
	int        dnb;
	int        xb, yb;
	int        i, l;
	char       *abc;

	if (y > 4)
		ispisi_rezultat(kriz);

	memcpy(krizb, kriz, sizeof(kriz_type));
	memcpy(datab, data, sizeof(data_type));
	dnb = dn; xb = x; yb = y;

	for (i = 1; i <= dn; i++) {
		if (!strcmp(data[i], data[i - 1]))
			continue;
		if (ubaci(kriz, data, &dn, i, &x, &y)) {
			do_the_mega_loop(kriz, data, dn, x, y);

			memcpy(kriz, krizb, sizeof(kriz_type));
			memcpy(data, datab, sizeof(data_type));
			dn = dnb; x = xb; y = yb;
		}
	}

	if (!x)
		if (!y) {
			kriz[0][0] = CRNO;
			do_the_mega_loop(kriz, data, dn, 1, 0);
		} else if (kriz[y - 1][0] != CRNO) {
			abc = vert(kriz, 0, y - 1);
			l = exact_data(data, dn, abc, 0);
			free(abc);
			if (l) {
				copy_data(data, dn, data, &dn, l);
				kriz[y][0] = CRNO;
				do_the_mega_loop(kriz, data, dn, 1, y);
			}
		}
}

void main(void)
{
	unesi_podatke();

	memset(kriz, NOT_USED, sizeof(kriz_type));

	do_the_mega_loop(kriz, data, dn, 0, 0);

	ispisi_ne();
}

KRIZ.PAS

{$A+,B-,D-,E-,F-,G+,I+,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X+,Y-}
program krizaljka;

const
     DIMENSION = 5;          {dimenzije krizaljke}
     MAXWORDS  = 50;         {maksimalni broj rijeci u rjecniku}
     IN_FILE   = 'kriz.in';  {ulazna datoteka}
     OUT_FILE  = 'kriz.out'; {izlazna datoteka}
     CRNO      = '*';        {oznaka za CRNO polje}
     NOTSET    = #1;         {#1 zbog inicijalizacije stringova s fillchar}

type
    kriz_node = string[1];
    data_node = string[DIMENSION];
    kriz_type = array [0..DIMENSION, 0..DIMENSION] of kriz_node;
    data_type = array [0..MAXWORDS] of data_node;

var
   ff  : text;
   kriz: kriz_type;
   data: data_type;
   dn  : integer;

procedure unesi;
var i: integer;
begin
     assign(ff, IN_FILE);
     reset(ff);
     readln(ff, dn);
     for i := 1 to dn do
         readln(ff, data[i]);
     data[0] := CRNO; {bilo koji string koji nije dozvoljena rijec}
     close(ff);
end;

procedure kraj(kriz: kriz_type);
var i, j: integer;
begin
     assign(ff, OUT_FILE);
     rewrite(ff);
     writeln(ff, 1);
     for j := 1 to DIMENSION do
     begin
          for i := 1 to DIMENSION do
              write(ff, kriz[j, i]:2);
          writeln(ff);
     end;
     close(ff);
     halt;
end;

procedure copy_data(data: data_type; dn: integer; var data2: data_type; var dn2: integer; except: integer);
var i: integer;
begin
     dn2 := 0;
     for i := 1 to dn do
     begin
          if i = except then continue;
          inc(dn2);
          data2[dn2] := data[i];
     end;
end;

function vert(kriz: kriz_type; x, y: integer): data_node;
var
   i, yc: integer;
   abc  : data_node;
begin
     yc := y - 1;
     while (yc > 0) and (kriz[yc, x] <> CRNO) do
           dec(yc);

     abc := '';
     for i := yc + 1 to y do
         abc := concat(abc, copy(kriz[i, x], 1, 1));

     vert := abc;
end;

function exact_data(data: data_type; dn: integer; what: data_node; whatnot: integer): integer;
var i: integer;
begin
     for i := 1 to dn do
         if (data[i] = what) and (i <> whatnot) then
         begin
              exact_data := i;
              exit;
         end;
     exact_data := 0;
end;

function apropos_data(data: data_type; dn: integer;
                      what: data_node): integer;
var i: integer;
begin
     for i := 1 to dn do
         if pos(what, data[i]) = 1 then
         begin
              apropos_data := i;
              exit;
         end;
     apropos_data := 0;
end;

function kriz_correct(kriz: kriz_type; var dt: data_type; var d: integer;
                      x, y: integer): boolean;
var
   l  : integer;
   abc: data_node;
begin
     while (x <= DIMENSION) and (kriz[y, x] <> NOTSET) do {check vertically}

     begin
          if kriz[y, x] <> CRNO then
          begin
               abc := vert(kriz, x, y);
               if y = DIMENSION then l := exact_data(dt, d, abc, 0)
                                else l := apropos_data(dt, d, abc);
               if l = 0 then begin kriz_correct := false; exit; end;
               if y = DIMENSION then copy_data(dt, d, dt, d, l);
          end;
          inc(x);
     end;

     kriz_correct := true;
end;

function ins(var kriz: kriz_type; var dt: data_type; var d: integer;
                 what: integer; var x, y: integer): boolean;
var i, l: integer;
begin
     if length(dt[what]) > DIMENSION - x + 1 then {da li ima mjesta?}
     begin
          ins := false;
          exit;
     end;

     l := 0;
     if (y > 1) and (x + length(dt[what]) <= DIMENSION) then
     begin {provjere vezane uz CRNO polje}
          if kriz[y - 1, x + length(dt[what])] = CRNO then
          begin  {nemozemo imati dva CRNA polja jedno iznad drugog}
               ins := false;
               exit;
          end;

          l := exact_data(dt, d,
                          vert(kriz, x + length(dt[what]), y - 1), what);
          if l = 0 then
          begin {rijec iznad crnog polja ne postoji!}
               ins := false;
               exit;
          end;
     end;

     for i := 1 to length(dt[what]) do
         kriz[y, x + i - 1] := copy(dt[what], i, 1);
     inc(x, length(dt[what]));

     {postavljanje novih koordinata}
     if x <= DIMENSION then begin kriz[y, x] := CRNO; inc(x); end;
     if x >  DIMENSION then begin x := 1; inc(y); end;

     copy_data(dt, d, dt, d, what); {izbacivanje upotrebljene rijeci}
     if l > 0 then {izbacivanje nadjene rjeci iznad CRNOG polja}
     begin
          if l > what then dec(l); {sve lijevo od what se pomaklo u desno}
          copy_data(dt, d, dt, d, l);
     end;

     ins := true;
end;

procedure rek(kriz: kriz_type; dt: data_type; d, x, y: integer);
var
   i, j  : integer;
   datab : data_type;  {backup - rjecnik}
   dnb   : integer;    {backup - broj rijeci u rjecniku}
   krizb : kriz_type;  {backup - krizaljka}
   xb, yb: integer;    {backup - koordinate}
begin
     datab := dt;
     dnb   := d;
     krizb := kriz;
     xb := x;
     yb := y;

     for i := 1 to d do
     begin
          if dt[i - 1] = dt[i] then continue;

          if ins(kriz, dt, d, i, x, y) then
          begin
               if kriz_correct(kriz, dt, d, xb, yb) then
               begin
                    if kriz[DIMENSION, DIMENSION] <> NOTSET then
                       kraj(kriz);
                    rek(kriz, dt, d, x, y);
               end;

               dt := datab;
               d  := dnb;
               kriz := krizb;
               x := xb;
               y := yb;
          end;
     end;

     if (x = 1) and (kriz[y - 1, 1] <> CRNO) then
     begin
          j := exact_data(dt, d, vert(kriz, 1, y - 1), 0); {fixing backup}
          if j = 0 then exit;                              {fixing backup}
          copy_data(datab, dnb, datab, dnb, j);            {fixing backup}
          kriz[y, 1]  := CRNO;                             {fixing backup}
          krizb[y, 1] := CRNO;                             {fixing backup}
          x := 2;                                          {fixing backup}
          for i := 1 to dn do
          begin
               if dt[i - 1] = dt[i] then continue;

               if ins(kriz, dt, d, i, x, y) then
               begin
                    if kriz_correct(kriz, dt, d, xb, yb) then
                    begin
                         if kriz[DIMENSION, DIMENSION] <> NOTSET then
                            kraj(kriz); {gotovo!}
                         rek(kriz, dt, d, x, y);
                    end;

                    dt := datab; d := dnb;
                    kriz := krizb;
                    x := 2; y := yb;
               end;
          end;
     end;
end;

procedure sort_data(var data: data_type; dn: integer);
var
   i, j: integer;
   t   : string[5];
begin
     for i := 1 to dn - 1 do {bubble sort}
         for j := i + 1 to dn do
             if data[i] > data[j] then
                begin t := data[i]; data[i] := data[j]; data[j] := t; end;
end;

begin
     unesi;
     sort_data(data, dn);
     fillchar(kriz, sizeof(kriz), NOTSET);

     rek(kriz, data, dn, 1, 1);

     assign(ff, OUT_FILE); {ovo se izvrsava samo ako nije nadjeno rjesenje}
     rewrite(ff);
     writeln(ff, 0);
     close(ff);
end.

Test podaci

KRIZ1.IN
KRIZ2.IN
KRIZ3.IN
KRIZ4.IN
KRIZ5.IN
KRIZ6.IN
10
cibnn
fnr
glxii
acxtn
gtg
ci
ykyf
hcazz
y
onxdv

10
aanag
eegca
anama
bmama
aaraa
mmagc
conar
abcde
draga
nmore

16
is
amara
ob
mom
ro
l
al
l
r
a
rotm
miora
or
ast
almo
bo

27
qsss
caaw
mpow
iuzw
iwow
lrbwb
mcuz
pqqq
qfs
stid
bm
s
o
d
iioi
a
bab
boris
zid
islo
mik
ra
lz
ukj
ij
as
u

50
p
ch
ad
lp
or
gkna
qsss
caaw
mpow
iuzw
iwow
qar
c
q
lrbwb
mcuz
pqqq
qfs
stid
a
ijk
b
eim
lm
defgh
bfj
no
iwpig
zaiqz
nzstz
viwxp
dtvxv
imhkx
naiay
aznme
xzsgx
jxmcm
kozfd
ydvuk
ybgis
kjecu
tcqxp
zmymn
mlxcz
kgyab
zcpnj
btcdh
vygnp
zuhhc
ikvzb

50
wgk
wwfor
aaas
gueeq
ulwvt
rwwaa
htdd
eglc
hxddx
vsts
ako
josip
kvar
mpow
iuzw
iwow
rosa
a
pqqq
qfs
stid
o
moral
majka
cx
x
irc
okovi
ai
lop
qsss
caaw
lrbwb
mcuz
ym
md
qc
gw
kf
aq
pi
ja
jx
nc
tg
qt
vw
wr
un
lt

KRIZ1.OUT
KRIZ2.OUT
KRIZ3.OUT
KRIZ4.OUT
KRIZ5.OUT
KRIZ6.OUT
0

1
abcde
nmore
aanag
mmagc
aaraa

1
amara
*is*l
rotm*
or*ob
*almo

1
boris
a*as*
bm*lz
*iioi
ukj*d

1
a*b*c
defgh
*ijk*
lm*no
p*qar

1
moral
ako*o
josip
kvar*
ai*cx

10 bodova
14 bodova
16 bodova
20 bodova
25 bodova
25 bodova