Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int sqr[51][51], n, k, t;
  6. bool row_safe[51][51], col_safe[51][51], solved;
  7.  
  8. void solver(int row, int col, int m)
  9. {
  10.     if (row == n && col == n + 1 && m == k && !solved)
  11.     {
  12.         solved = true;
  13.         cout << "Case #" << t << ": "
  14.              << "POSSIBLE\n";
  15.         for (int i = 1; i <= n; ++i)
  16.         {
  17.             for (int j = 1; j <= n; ++j)
  18.             {
  19.                 cout << sqr[i][j] << " ";
  20.             }
  21.             cout << "\n";
  22.         }
  23.         return;
  24.     }
  25.     else if (row > n)
  26.     {
  27.         return;
  28.     }
  29.     else if (col > n)
  30.     {
  31.         solver(row + 1, 1, m);
  32.     }
  33.     for (int i = 1; i <= n && !solved; ++i)
  34.     {
  35.         if (!row_safe[row][i] && !col_safe[col][i])
  36.         {
  37.             row_safe[row][i] = col_safe[col][i] = true;
  38.             if (row == col)
  39.             {
  40.                 m += i;
  41.             }
  42.             sqr[row][col] = i;
  43.  
  44.             solver(row, col + 1, m);
  45.  
  46.             row_safe[row][i] = col_safe[col][i] = false;
  47.             if (row == col)
  48.             {
  49.                 m -= i;
  50.             }
  51.             sqr[row][col] = 0;
  52.         }
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58.     int T;
  59.     cin >> T;
  60.     for (t = 1; t <= T; ++t)
  61.     {
  62.         cin >> n >> k;
  63.         solver(1, 1, 0);
  64.         if (!solved)
  65.         {
  66.             cout << "Case #" << t << ": "
  67.                  << "IMPOSSIBLE\n";
  68.         }
  69.         solved = false;
  70.     }
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement