cjelobrojna mreza

[Bug]

zanima me kako odrediti broj najkracih puteva u cjelobrojnoj mrezi od ishodista do (a,b), a da ne prolaze segmentima [(p,q),(p+1)] i [(r,s),(r,s+1)]

_________________
Everybody Dies...
Nobody is perfect...

Non scholae, sed vitae discimus

[vili]

Prvo odrediš ukupan broj puteva od (0,0) do (a,b), to je a+b povrh a.

Sad ovisno dal je tvoje pitanje bilo da ne smije prolaziti niti jednim od ova dva segmenta, ili točno oba, u prvom slučaju računaš preko fui-a, a u drugom oduzmeš od ukupnog broja broj puteva koji prolaze kroz oba segmenta.

Recimo, broj puteva koji idu segmentom [(p,q),(p+1,q)] je broj puteva od (0,0) do (p,q) puta broj puteva od (p+1,q) do (a,b) znači (p+q povrh p)*(a-p-1+b-q povrh b-q). Analogno izračunaš broj ostalih puteva koji prolaze segmentima.

[Bug]

zanima me kako izracunati preko fui a1 presjek a2 za ta dva segmenta

_________________
Everybody Dies...
Nobody is perfect...

Non scholae, sed vitae discimus

[vili]

Pogledaš kako se ti segmenti odnose, odn dal uopće iz jednoga možeš doći u drugi (dal ti je presjek neprazan), naravno, ako se krećeš najkraćim putem.
Ako je (p+1<=r i q<=s) ili (r<=p i s+1<=q) (nacrtaj si pa će ti bit jasnije) onda potoji barem jedan put koji prolazi kroz oba segmenta.
Onda je broj puteva koji prolazi kroz oba segmenta (pretpostavljam da u zadatku imaš konkretne brojeve, pa neka je BSO p+1<=r i q<=s, drugi slučaj napraviš analogno) jednak (p+q povrh p)*(r+s-p-1-q povrh s-q)*(a+b-r-s-1 povrh a-r).

Nadam se da je sad nešto jasnije