API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
49
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.64 KB | None | 0 0
raw download clone embed print report
  1. /* /0   1    2    [0]  4  2  4------ */
  2. /* 3    4    3    5    3 [0] 3------- */
  3. /* 2    [0]  3    3    2  4  2------ */
  4. /* 2    1    [0]  4    5  3  4------- */
  5. /* [0]  1    2    3   /0  1  3    */
  6. /* 2    3    2    3    5  5 [0] -------- */
  7. /* 3    /0   /0   1   [0] 3  5    */
  8. /*             | */
  9. /*         | */
  10. /*         | */
  11.  
  12. /* 20 */
  13.  
  14. #include <stdio.h>
  15. #include <stdbool.h>
  16.  
  17. #define zerobarre -1
  18. #define zeroencadre -2
  19.  
  20. void liretableau(int(*)[100], int);
  21. void savetab(int(*)[100], int(*)[100], int);
  22. void reduire(int(*)[100], int);
  23. bool fini(int(*)[100], int);
  24. int minligne(int*, int);
  25. int mincol(int(*)[100], int, int);
  26. void retminlig(int(*)[100], int);
  27. void retmincol(int(*)[100], int);
  28. int nbzerononbar(int*, int);
  29. int choilig(int(*)[100], int);
  30. int encadr(int(*)[100], int, int);
  31. void barrer(int(*)[100], int, int, int);
  32. bool peutbarrer(int(*)[100], int);
  33. void encetbarr(int(*)[100], int);
  34. void marqulig(int(*)[100], bool*, int);
  35. int marqucolig(int(*)[100], bool*, bool*, int);
  36. int marquligol(int(*)[100], bool*, bool*, int);
  37. void marqetbar(int(*)[100], int(*)[100], int);
  38. int detmintab(int(*)[100], int(*)[100], int);
  39. void retmintab(int(*)[100], int(*)[100], int, int);
  40. void ajoutertabdeuf(int(*)[100], int(*)[100], int, int);
  41. void etape3(int(*)[100], int(*)[100], int);
  42. int finir(int(*)[100], int(*)[100], int);
  43. void ecriretableau(int(*)[100], int);
  44.  
  45. int main(void)
  46. {
  47.   int tab[100][100], tabbak[100][100];
  48.   int taille;
  49.   int barre[100][100];
  50.  
  51.   scanf("%d",&taille);
  52.  
  53.   for(int i=0;i<taille;i++)
  54.     for(int j=0;i<taille;i++)
  55.       barre[i][j]=0;
  56.  
  57.   liretableau(tab,taille);
  58.  
  59.   savetab(tab, tabbak, taille);
  60.  
  61.   reduire(tab,taille);
  62.  
  63.   while(!fini(tab, taille))
  64.     {
  65.   encetbarr(tab, taille);  
  66.      
  67.       if(!fini(tab, taille))
  68.     {
  69.       marqetbar(tab, barre, taille);
  70.       etape3(tab, barre, taille);
  71.     }
  72.     }
  73.  
  74.   ecriretableau(tab, taille);
  75.  
  76.   printf("%d\n",finir(tab, tabbak, taille));
  77.  
  78.   return 0;
  79. }
  80.  
  81. void liretableau(int tab[][100], int taille)
  82. {
  83.   for(int i=0;i<taille;i++)
  84.     for(int j=0;j<taille;j++)
  85.       scanf("%d",&(tab[i][j]));
  86. }
  87.  
  88. void savetab(int tab[][100], int tabbak[][100], int taille)
  89. {
  90.   for(int i=0;i<taille;i++)
  91.     for(int j=0;j<taille;j++)
  92.       tabbak[i][j]=tab[i][j];
  93. }
  94.  
  95. int minligne(int* ligne, int taille)
  96. {
  97.   int min=ligne[0];
  98.  
  99.   for(int i=1;i<taille;i++)
  100.     if(ligne[i]<min)
  101.       min=ligne[i];
  102.  
  103.   return min;
  104. }
  105.  
  106. int mincol(int tab[][100], int col, int taille)
  107. {
  108.   int min=tab[0][col];
  109.  
  110.   for(int i=1;i<taille;i++)
  111.     if(tab[i][col]<min)
  112.       min=tab[i][col];
  113.  
  114.   return min;
  115. }
  116.  
  117. void retminlig(int tab[][100], int taille)
  118. {
  119.   int min;
  120.  
  121.   for(int i=0;i<taille;i++)
  122.     {
  123.       min=minligne(tab[i],taille);
  124.       for(int j=0;j<taille;j++)
  125.     tab[i][j]-=min;
  126.     }
  127. }
  128.  
  129. void retmincol(int tab[][100], int taille)
  130. {
  131.   int min;
  132.  
  133.   for(int i=0;i<taille;i++)
  134.     {
  135.       min=mincol(tab,i,taille);
  136.       for(int j=0;j<taille;j++)
  137.     tab[j][i]-=min;
  138.     }
  139. }
  140.  
  141. void reduire(int tab[][100], int taille)
  142. {
  143.   retminlig(tab,taille);
  144.   retmincol(tab,taille);
  145. }
  146.  
  147. int nbzerononbar(int* ligne, int taille)
  148. {
  149.   int nb=0;
  150.  
  151.   for(int i=0;i<taille;i++)
  152.     if(ligne[i]==0 || ligne[i]==zeroencadre)
  153.       nb++;
  154.  
  155.   return nb;
  156. }
  157.  
  158. int choilig(int tab[][100], int taille)
  159. {
  160.   int min=nbzerononbar(tab[0], taille), minind=0;
  161.  
  162.   for(int i=1;i<taille;i++)
  163.     if(nbzerononbar(tab[i],taille)<min)
  164.       {
  165.     min=nbzerononbar(tab[i],taille);
  166.     minind=i;
  167.       }
  168.  
  169.   return minind;
  170. }
  171.  
  172. int encadr(int tab[][100], int ligne, int taille)
  173. {
  174.   int i;
  175.  
  176.   while(tab[ligne][i]!=0 && i<taille)
  177.     i++;
  178.  
  179.   tab[ligne][i]=zeroencadre;
  180.  
  181.   return i;
  182. }
  183.  
  184. void barrer(int tab[][100], int ligne, int col, int taille)
  185. {
  186.   for(int i=0;i<taille;i++)
  187.     {
  188.       if(tab[ligne][i]==0)
  189.     tab[ligne][i]=zerobarre;
  190.       if(tab[i][col]==0)
  191.     tab[i][col]=zerobarre;
  192.     }
  193. }
  194.  
  195. bool peutbarrer(int tab[][100], int taille)
  196. {
  197.   return (nbzerononbar(tab[choilig(tab, taille)],taille)!=0);
  198. }
  199.  
  200. void encetbarr(int tab[][100], int taille)
  201. {
  202.   int l, k;
  203.   while(peutbarrer(tab, taille))
  204.     {
  205.       l=choilig(tab, taille);
  206.       k=encadr(tab, l, taille);
  207.       barrer(tab, l, k, taille);  
  208.     }    
  209. }
  210.  
  211. bool fini(int tab[][100], int taille)
  212. {
  213.   int nb;
  214.  
  215.   for(int i=0;i<taille;i++)
  216.     {
  217.       nb=0;
  218.       for(int j=0;j<taille;j++)
  219.     if(tab[i][j]==zeroencadre)
  220.       nb++;
  221.       /* if(nb!==1) */
  222.     /* return false;*/
  223.     }
  224.  
  225.   for(int i=0;i<taille;i++)
  226.     {
  227.       nb=0;
  228.       for(int j=0;j<taille;j++)
  229.     if(tab[j][i]==zeroencadre)
  230.       nb++;
  231.       /* if(nb!==1) */
  232.       /*    return false; */
  233.       /* j'ai pas vraiment cherché à comprendre ton programme mais je pense que ton erreur vient de là */
  234.     }
  235.  
  236.   return true;
  237. }
  238.  
  239. int nbzeroencad(int* ligne, int taille)
  240. {
  241.   int nb=0;
  242.  
  243.   for(int i=0;i<taille;i++)
  244.     if(ligne[i]==zeroencadre)
  245.       nb++;
  246.  
  247.   return nb;
  248. }
  249.  
  250. void marqulig(int tab[][100], bool* tablignes, int taille)
  251. {
  252.   for(int i=0;i<taille;i++)
  253.     if(nbzeroencad(tab[i], taille)==0)
  254.       tablignes[i]=true;
  255. }
  256.  
  257. int marqucolig(int tab[][100], bool* tablignes, bool* tabcol, int taille)
  258. {
  259.   int som=0;
  260.  
  261.   for(int i=0;i<taille;i++)
  262.     if(tablignes[i]==true)
  263.       for(int j=0;j<taille;j++)
  264.     if(tab[i][j]==zerobarre)
  265.       if(tabcol[j]==false)
  266.         {
  267.           tabcol[j]=true;
  268.           som++;
  269.         }
  270.  
  271.   return som;
  272. }
  273.  
  274. int marquligol(int tab[][100], bool* tablignes, bool* tabcol, int taille)
  275. {
  276.   int som=0;
  277.  
  278.   for(int i=0;i<taille;i++)
  279.     if(tabcol[i]==true)
  280.       for(int j=0;j<taille;j++)
  281.     if(tab[j][i]==zeroencadre)
  282.       if(tablignes[j]==false)
  283.         {
  284.           tablignes[j]=true;
  285.           som++;
  286.         }
  287.  
  288.   return som;
  289. }
  290.  
  291. void marqetbar(int tab[][100], int barre[][100], int taille)
  292. {
  293.   int k,l;
  294.   bool tablignes[taille], tabcol[taille];
  295.  
  296.   for(int i=0;i<taille;i++)
  297.     tablignes[i]=tabcol[i]=false;
  298.  
  299.   marqulig(tab, tablignes, taille);
  300.  
  301.   do
  302.     {
  303.       l=marqucolig(tab, tablignes, tabcol, taille);
  304.       k=marquligol(tab, tablignes, tabcol, taille);
  305.     }
  306.   while(k!=0 || l!=0);
  307.  
  308.   for(int i=0;i<taille;i++)
  309.     if(tablignes[i]==true)
  310.       for(int j=0;j<taille;j++)
  311.     barre[i][j]++;
  312.  
  313.   for(int i=0;i<taille;i++)
  314.     if(tabcol[i]==true)
  315.       for(int j=0;j<taille;j++)
  316.     barre[j][i]++;
  317. }
  318.  
  319. int detmintab(int tab[][100], int barre[][100], int taille)
  320. {
  321.   int min,k=0,l=0;
  322.   bool premin=false;
  323.  
  324.   while(k<taille && premin==false)
  325.     {
  326.       while(l<taille && premin==false)
  327.     {
  328.       if(barre[k][l]!=2)
  329.         {
  330.           min=tab[k][l];
  331.           premin=true;
  332.         }
  333.       l++;
  334.     }
  335.       k++;
  336.     }
  337.  
  338.   for(int i=0;i<taille;i++)
  339.     for(int j=0;j<taille;j++)
  340.       if(barre[i][j]!=2 && tab[i][j]<min)
  341.     min=tab[i][j];
  342.  
  343.   return min;
  344. }
  345.  
  346. void retmintab(int tab[][100], int barre[][100], int min, int taille)
  347. {
  348.   for(int i=0;i<taille;i++)
  349.     for(int j=0;j<taille;j++)
  350.       if(barre[i][j]!=2)
  351.     tab[i][j]-=min;
  352. }
  353.  
  354. void ajoutertabdeuf(int tab[][100], int barre[][100], int min, int taille)
  355. {
  356.   for(int i=0;i<taille;i++)
  357.     for(int j=0;j<taille;j++)
  358.       if(barre[i][j]==2)
  359.     tab[i][j]+=min;
  360.  
  361. }
  362.  
  363. void etape3(int tab[][100], int barre[][100], int taille)
  364. {
  365.   int m;
  366.  
  367.   m=detmintab(tab, barre, taille);
  368.   retmintab(tab, barre, m, taille);
  369.   ajoutertabdeuf(tab, barre, m, taille);
  370. }
  371.  
  372. int finir(int tab[][100], int tabbak[][100], int taille)
  373. {
  374.   int som=0;
  375.   for(int i=0;i<taille;i++)
  376.     for(int j=0;j<taille;j++)
  377.       if(tab[i][j]==zeroencadre)
  378.     som+=tabbak[i][j];
  379.  
  380.   return som;
  381. }
  382.  
  383. void ecriretableau(int tab[][100], int taille)
  384. {
  385.   for(int i=0;i<taille;i++)
  386.     for(int j=0;j<taille;j++)
  387.       {
  388.     printf("%d ",tab[i][j]);
  389.     if(j==(taille-1))
  390.       printf("\n");
  391.       }
  392. }
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!