拉丁矩陣問題

 ">**問題描述

*現有n 種不同形狀的寶石，每種寶石有足夠多顆。

*将這些寶石排列成m行n 列的一個矩陣，m≤n，使矩陣中每一行和每一列的寶石都沒有相同形狀。

*設計一個算法，計算出對于給定的m和n，有多少種不同的寶石排列方案。

**程式設計任務

*對于給定的m和n，計算出不同的寶石排列方案數。

**資料輸入 input.txt

*第一行有兩個正整數m和n,0<m<=9

**資料輸出 output.txt

*将計算出的寶石排列方案數輸出到檔案

**解決思路

*回溯，主要是行和列一起回溯

*二維數組board[m][n]存儲寶石矩陣。每行初始化為機關排列，第一行從上到下為1,2，...m

**參考

*<a href="http://longgongshiye.blog.163.com/blog/static/17148259720117178143225/" target="_blank" rel="external nofollow" target="_blank"> 參考代碼 </a>

*/

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

using namespace std;

int const MAX = 9;

typedef int ARRAY2D[MAX][MAX];

ARRAY2D board;

int N(0), M(0),Count(0);

inline void readfile(const string &filename)

{

   FILE *stream;

   std::ios::sync_with_stdio(false);//加速

   freopen_s(&stream,filename.c_str(), "r", stdin);

   //scanf("%d",&a),cin可以跳過不合法字元

   cin >> M >> N;

   fclose(stdin);

}

template <typename T>

inline int writefile(string filename, T n)

{

   //freopen(filename.c_str(), "r", stdout);

   //fclose(stdout);

   ofstream ofile(filename.c_str(), ios_base::binary | ios_base::out);

   if (!ofile)

   {

       cerr << "cannot open file!\n";

       exit(1);

   }

   ofile << n;

   cout << "write over." << endl;

   return 0;

}

int bound(int r, int c)

{

   for (int i = 1; i < r; ++i)

       if (board[i][c] == board[r][c]) return 0;

   return 1;

}

void backtrack(int r, int c)

{

   if (r > M){

       ++Count;

       for (int i = 1; i <= M; ++i){

           for (int j = 1; j <= N; ++j)

               printf("%d", board[i][j]);

           printf("\n");

       }

       printf("\n");

       return;    

   }

   if (c > N){

       backtrack(r + 1, 1);

   }

   for (int i = c; i <= N; ++i){

       swap(board[r][c], board[r][i]);      //要先交換

       if (bound(r, c)) backtrack(r, c + 1);

       swap(board[r][c], board[r][i]);

   }

}

int main()

{

   string input = "input.txt";

   string output = "output.txt";

   readfile(input);             //get M and N

   for (int i = 1; i <= N; ++i){

       for (int j = 1; j <= N; ++j){

           board[i][j] = j;

       }

   }

   for (int i = 1; i <= N; ++i)

       swap(board[i][1], board[i][i]);

   backtrack(1, 1);

   writefile(output, Count);

   system("pause");

   return 0;

}