CPP   126

testbug

Guest on 6th June 2022 01:12:44 AM

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. int a, b, ans;
  6.  
  7. void dfss(int p, int q, int m, int d, int f)
  8. {
  9.         int i, j;
  10.         if(d >= ans)
  11.         {
  12.                 return;
  13.         }
  14.         if(f && p == a && q == b)
  15.         {
  16.                 ans = d;
  17.         }
  18.         for(i=0; i<=q; i++)
  19.         {
  20.                 if(i * 3 > m)
  21.                 {
  22.                         break;
  23.                 }
  24.                 for(j=i; j<=p; j++)
  25.                 {
  26.                         if(j == 0 || (j != p && p-j < q-i))
  27.                         {
  28.                                 continue;
  29.                         }
  30.                         if(i*2 + j > m)
  31.                         {
  32.                                 break;
  33.                         }
  34.                         dfss(a-p+j, b-q+i, m, d+1, 1-f);
  35.                 }
  36.         }
  37. }
  38.  
  39. void dfs(int p, int q, int m, int d, int f)
  40. {
  41.         int i, j;
  42.         if(d >= ans)
  43.         {
  44.                 return;
  45.         }
  46.         if(f && p == a && q == b)
  47.         {
  48.                 ans = d;
  49.         }
  50.         if(q > p)
  51.         {
  52.                 dfs(a, q, m, d+1, 1-f);
  53.                 return;
  54.         }
  55.         for(i=0; i<=q; i++)
  56.         {
  57.                 if(i * 3 > m)
  58.                 {
  59.                         break;
  60.                 }
  61.                 for(j=i; p-j>=q-i||p==j; j++)
  62.                 {
  63.                         if(j == 0)
  64.                         {
  65.                                 continue;
  66.                         }
  67.                         if(i*2 + j > m)
  68.                         {
  69.                                 break;
  70.                         }
  71.                         dfs(a-p+j, b-q+i, m, d+1, 1-f);
  72.                 }
  73.         }
  74. }
  75.  
  76. int main()
  77. {
  78.         int d, x;
  79.         int i, j, k, t, r;
  80.         int c, p, q, m;
  81.         srand(time(NULL));
  82.         for(; ; )
  83.         {
  84.                 a = rand() % 12;
  85.                 b = rand() % 10;
  86.                 m = rand() % 15;
  87.                 printf("%d %d %d\n", a, b, m);
  88.                 if(a < b)
  89.                 {
  90.                         printf("0\nNo solution!\n");
  91.                         printf("0\nNo solution!\n");
  92.                         system("pause");
  93.                         continue;
  94.                 }
  95.                 if(a == b && a == 0)
  96.                 {
  97.                         printf("0\nCross river!\n");
  98.                         printf("0\nCross river!\n");
  99.                         system("pause");
  100.                         continue;
  101.                 }
  102.                 ans = 16;
  103.                 dfss(a, b, m, 0, 0);
  104.                 if(ans == 16)
  105.                 {
  106.                         printf("0\nNo solution!\n");
  107.                 }
  108.                 else
  109.                 {
  110.                         printf("%d\nCross river!\n", ans);
  111.                 }
  112.                 ans = 16;
  113.                 dfs(a, b, m, 0, 0);
  114.                 if(ans == 16)
  115.                 {
  116.                         printf("0\nNo solution!\n");
  117.                 }
  118.                 else
  119.                 {
  120.                         printf("%d\nCross river!\n", ans);
  121.                 }
  122.                 system("pause");
  123.         }
  124.         return 0;
  125. }

Raw Paste


Login or Register to edit or fork this paste. It's free.