API tools faq
paste
Advertisement
elica123

Untitled

elica123
Aug 11th, 2018
117
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.44 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. RJESENJE PRVE GRUPE:
  3. Gusari prate kartu da dođu do skrivenog blaga. Međutim, bili su neoprezni pa su kartu zaprljali vinom.
  4. Cilj je napisati program koji će \emph{očistiti} kartu. Preciznije, zaprljani dio karte je zapisan u matrici
  5. znakova (\texttt{char}) tipa $m\times n$ ($m,n\leqslant 50$). Sa znakom \texttt{'X'} je označavan put, s \texttt{'*'} mrlja,
  6. te s \texttt{'0'} ostatak matrice.
  7. Put uvijek počinje iz gornjeg lijevog kuta matrice (mjesto $(0,0)$) te iz svake točke može ići dalje samo desno ili dolje, tj.~iz mjesta
  8. $(i,j)$ možemo ići ili u $(i+1,j)$ ili u $(i,j+1)$. Nadalje, put ne staje u tom dijelu karte već je kraj u nekoj točki ruba dane matrice.
  9. Mrlje su realizirane uvijek kvadratnom podmatricom tipa $2\times 2$ (čiji su svi elementi jednaki \texttt{'*'}) pri čemu su za
  10. barem jedno polje udaljene od ruba matrice, te se nikoje dvije mrlje ne dodiruju.
  11. Dakle, put ili ne prolazi uopće kroz mrlju ili točno postoji jedan ulaz i jedan izlaz puta iz mrlje.
  12. Ako put ne prolazi kroz mrlju, potrebno je postaviti sve elemente mrlje na \texttt{'0'}. U suprotnom, put je potrebno povezati tako da je
  13. potrebno najmanje znakova \texttt{'X'} (ukoliko postoji više mogućnosti, sami izaberite jedno od njih), dok se preostala polja postavljaju na \texttt{'0'}.
  14.  
  15. Potrebno je napisati funkciju \texttt{ocisti} koja prima kao argument
  16. gore opisanu matricu znakova i njene dimenzije koju \emph{čisti} na gore opisan način. Napišite i dio koda koji demonstrira poziv funkcije, pri čemu
  17. možete pretpostaviti da su svi potrebni podaci već učitani.
  18.  
  19. Za rjesenja preostalih grupa samo treba znakove 'X', '*' i '0' zamijeniti s odgovarajucim znakovima.
  20.  
  21. NAPOMENA: prezentiramo tri rjesenja. Naravno, nisu to sve mogucnosti za rjesavanje zadatka. Na primjer, zadatak se elegantno moze rijesiti koriteci rekurzivnu
  22. funkciju. Probajte :)
  23. */
  24.  
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28.  
  29.  
  30.  
  31.  
  32. /*FUNKCIJA KOJA NIJE TREBALA ZA RJESENJE ZADATKA, ALI JE KORISTIMO ZA TESTIRANJE*/
  33.  
  34. void ispis(char karta[][50], int m, int n)
  35. {
  36. int i, j;
  37.  
  38. for(i=0; i<m; i++){
  39. for(j=0; j<n; j++){
  40. printf("%c ", karta[i][j]);
  41. }
  42. printf("\n");
  43. }
  44. printf("\n");
  45. }
  46. /*************************************************************/
  47.  
  48.  
  49.  
  50. /*POMOCNA FUNKCIJA KOJA SE KORISTI U 1. I 2. RJESENJU*/
  51. /*polja mrlje stavljamo na neutralnu vrijednost '0'*/
  52. /*ne trebamo u argument stavljati dimenzije matrice jer znamo da je mrlja dimenzije 2x2 i da je udaljena od rubova*/
  53.  
  54. void mrlju_na_nula(char karta[][50], int i, int j)
  55. {
  56. karta[i][j]=karta[i+1][j]=karta[i][j+1]=karta[i+1][j+1]='0';
  57.  
  58. return;
  59. }
  60. /*************************************************************/
  61.  
  62.  
  63.  
  64.  
  65.  
  66. /*RJESENJE 1: ocisti1 i pomocne funkcije makni_mrlju i mrlju_na_nulu*/
  67. /*Prolazimo kroz matricu i trazimo '*'. Kako pretrazujemo od lijevo prema
  68. desno, te od gore prema dolje, to je '*' na koju naidjemo sigurno gornje
  69. lijevo polje mrlje. Zatim cijelu mrlju stavimo na '0', a potom koristimo funkciju
  70. makni_mrlju da vidimo gdje ce tocno doci 'X'.*/
  71.  
  72. void makni_mrlju(char karta[][50], int i, int j) //cesta greska je bila da se ovdje pise karta[50][50]
  73. {
  74. if(karta[i-1][j]=='X' && karta[i-1][j+1]!='X'){
  75. karta[i][j]='X';
  76. if(karta[i][j+2]=='X'){
  77. karta[i][j+1]='X';
  78. }
  79. else if(karta[i+2][j]=='X'){
  80. karta[i+1][j]='X';
  81. }
  82. else if(karta[i+1][j+2]=='X' || karta[i+2][j+1]=='X'){
  83. karta[i+1][j]='X';
  84. karta[i+1][j+1]='X';
  85. }
  86. }
  87. if(karta[i-1][j+1]=='X' && karta[i-1][j+2]!='X'){
  88. karta[i][j+1]='X';
  89. if(karta[i][j+2]!='X' && (karta[i+1][j+2]=='X' || karta[i+2][j+1]=='X')){
  90. karta[i+1][j+1]='X';
  91. }
  92. }
  93.  
  94.  
  95. if(karta[i][j-1]=='X' && karta[i+1][j-1]!='X'){
  96. karta[i][j]='X';
  97. if(karta[i+2][j]=='X'){
  98. karta[i+1][j]='X';
  99. }
  100. else if(karta[i][j+2]=='X'){
  101. karta[i][j+1]='X';
  102. }
  103. else if(karta[i+2][j+1]=='X' || karta[i+1][j+2]=='X'){
  104. karta[i+1][j]='X';
  105. karta[i+1][j+1]='X';
  106. }
  107. }
  108. if(karta[i+1][j-1]=='X' && karta[i+2][j-1]!='X'){
  109. karta[i+1][j]='X';
  110. if(karta[i+2][j]!='X' && (karta[i+2][j+1]=='X' || karta[i+1][j+2]=='X')){
  111. karta[i+1][j+1]='X';
  112. }
  113. }
  114.  
  115. return;
  116. }
  117.  
  118. void ocisti1(char karta[][50], int m, int n)
  119. {
  120. int i=0, j=0;
  121.  
  122. for(i=0; i<m; i++)
  123. for(j=0; j<n; j++)
  124. if(karta[i][j]=='*'){
  125. mrlju_na_nula(karta,i,j);
  126. makni_mrlju(karta,i,j);
  127. }
  128.  
  129. return;
  130. }
  131. /*************************************************************/
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139. /*RJESENJE 2: ocisti2 i pomocne funkcije prolaz_kroz_mrlju i mrlju_na_nulu*/
  140. /*Prolazimo kroz matricu i trazimo '*'. Kako pretrazujemo od lijevo prema
  141. desno, te od gore prema dolje, to je '*' na koju naidjemo sigurno gornje
  142. lijevo polje mrlje. Zatim cijelu mrlju stavimo na '0', a potom koristimo funkciju
  143. prolaz_kroz_mrlju koja vraca vrijednost 1 ako put prolazi kroz mrlju, te 0 ako ne
  144. prolazi. Ukoliko put prolazi kroz mrlju preko adrese se prenose indeksi mjesta ulaska
  145. u mrlju i izlaska iz mrlje.*/
  146.  
  147. int prolaz_kroz_mrlju(char karta[][50], int i, int j, int* iulaz, int* julaz, int* iizlaz, int* jizlaz)
  148. {
  149. int prolazi=0;
  150.  
  151. if(karta[i-1][j+1]=='X' && karta[i-1][j+2]!='X'){
  152. *iulaz=i;
  153. *julaz=j+1;
  154. prolazi=1;
  155. }
  156. else if(karta[i-1][j]=='X' && karta[i-1][j+1]!='X'){
  157. *iulaz=i;
  158. *julaz=j;
  159. prolazi=1;
  160. }
  161. if(karta[i+1][j-1]=='X' && karta[i+2][j-1]!='X'){
  162. *iulaz=i+1;
  163. *julaz=j;
  164. prolazi=1;
  165. }
  166. else if(karta[i][j-1]=='X' && karta[i+1][j-1]!='X'){
  167. *iulaz=i;
  168. *julaz=j;
  169. prolazi=1;
  170. }
  171.  
  172. if(!prolazi)
  173. return 0;
  174.  
  175. if(karta[i][j+2]=='X'){
  176. *iizlaz=i;
  177. *jizlaz=j+1;
  178. }
  179. else if(karta[i+1][j+2]=='X'){
  180. *iizlaz=i+1;
  181. *jizlaz=j+1;
  182. }
  183. else if(karta[i+2][j]=='X'){
  184. *iizlaz=i+1;
  185. *jizlaz=j;
  186. }
  187. else{
  188. *iizlaz=i+1;
  189. *jizlaz=j+1;
  190. }
  191.  
  192. return 1;
  193. }
  194.  
  195.  
  196. void ocisti2(char karta[][50], int m, int n)
  197. {
  198. int i=0, j=0, iu, ju, ii, ji, k;
  199.  
  200. for(i=0; i<m; i++)
  201. for(j=0; j<n; j++)
  202. if(karta[i][j]=='*'){
  203. mrlju_na_nula(karta,i,j);
  204. if(prolaz_kroz_mrlju(karta,i,j,&iu,&ju,&ii,&ji)){
  205. for(k=iu; k<=ii; k++)
  206. karta[k][ju]='X';
  207. for(k=ju; k<=ji; k++)
  208. karta[ii][k]='X';
  209. }
  210. }
  211.  
  212. return;
  213. }
  214. /*************************************************************/
  215.  
  216.  
  217.  
  218.  
  219.  
  220. /*RJESENJE 3: ocisti3*/
  221. /*Krecemo od mjesta (0,0) i pratimo put. Kad dodjemo do '*', onda odlucujemo gdje treba
  222. staviti 'X'.*/
  223.  
  224. void ocisti3(char karta[][50], int m, int n)
  225. {
  226. int i=0, j=0, ipom, jpom; //i, j su brojaci, a ipom i jpom nam sluze za izlazak iz petlje (vidi dolje if)
  227.  
  228. while(i<m && j<n){
  229. ipom=i;
  230. jpom=j;
  231.  
  232. if(j+1<n && karta[i][j+1]=='X')
  233. j++;
  234. else if(i+1<m && karta[i+1][j]=='X')
  235. i++;
  236. else if(i+1<m && j+1<n && karta[i][j+1]=='*' && karta[i+1][j]=='0')
  237. karta[i][++j]='X';
  238. else if(i+1<m && j+1<n && karta[i+1][j]=='*' && karta[i][j+1]=='0')
  239. karta[++i][j]='X';
  240. else if(i+1<m && j+1<n && karta[i][j+1]=='*' && karta[i+1][j]=='*'){ //ovo se ne moze dogoditi u prvom koraku, ali se moze u kasnijim koracima pojaviti pa je bitno ovo dobro napisati da "sredimo" cijelu mrlju dobro
  241. if(karta[i][j+2]=='X')
  242. karta[i][++j]='X';
  243. else
  244. karta[++i][j]='X';
  245. }
  246.  
  247. /*ako je donji uvjet ispunjen, znaci da nismo mijenjali poziciju sto znaci da smo dosli do kraja puta
  248. (ovo je potrebno jer put ne mora zavrsiti nuzno u mjestu (m-1,n-1)*/
  249. if(ipom==i && jpom==j)
  250. break;
  251. }
  252.  
  253. /*ukoliko je ostalo '*', stavljamo ih na '0' jer smo vec stavili 'X' gdje je potrebno*/
  254. for(i=0; i<m; i++)
  255. for(j=0; j<n; j++)
  256. if(karta[i][j]=='*')
  257. karta[i][j]='0';
  258.  
  259. return;
  260. }
  261. /*************************************************************/
  262.  
  263.  
  264.  
  265.  
  266. int main(void)
  267. {
  268. int m, n;
  269. char karta1[][50]={{'X','0','0','0','0','0','0','0'},
  270. {'X','X','*','*','X','*','*','0'},
  271. {'0','0','*','*','X','*','*','0'},
  272. {'0','0','0','0','X','X','X','X'},
  273. {'0','0','0','0','0','0','0','X'}};
  274. char karta2[][50]={{'X','0','0','0','0','0','0','0','0','0'},
  275. {'X','X','X','X','*','*','0','0','0','0'},
  276. {'0','*','*','0','*','*','0','*','*','0'},
  277. {'0','*','*','0','0','X','X','*','*','X'},
  278. {'0','0','0','0','0','0','0','0','0','X'}};
  279.  
  280. printf("\n\nPrvi primjer:\n");
  281. m=sizeof(karta1)/sizeof(*karta1);
  282. n=sizeof(*karta1)/sizeof(**karta1);
  283. ispis(karta1,m,n);
  284. ocisti1(karta1,m,n);
  285. ispis(karta1,m,n);
  286.  
  287. printf("\n\nDrugi primjer:\n");
  288. m=sizeof(karta2)/sizeof(*karta2);
  289. n=sizeof(*karta2)/sizeof(**karta2);
  290. ispis(karta2,m,n);
  291. ocisti1(karta2,m,n);
  292. ispis(karta2,m,n);
  293.  
  294. return 0;
  295. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!