本文共 1456 字,大约阅读时间需要 4 分钟。
/*dfs,需要注意输入的测试数据的格式。*/
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 using namespace std;18 const int INF = -0x3f3f3f3f;19 const int MaxN = 55;20 const int modPrime = 3046721;21 22 int n;23 int colorArr[10];24 char imap[10][10];25 int answer = 0;26 27 bool isAdjoinColor(int node, int color)28 {29 for (int i = 0; i < n; ++i)30 {31 if ((imap[node][i] == '1') && (color == colorArr[i]))32 {33 return true;34 }35 }36 return false;37 }38 39 void Solve(int nodeNum)40 {41 if (nodeNum == n)42 {43 ++answer;44 return;45 }46 for (int color = 1; color <= 4; ++color)47 {48 if (!isAdjoinColor(nodeNum, color))49 {50 colorArr[nodeNum] = color;51 Solve(nodeNum + 1);52 colorArr[nodeNum] = -1;53 }54 }55 }56 57 58 int main()59 {60 #ifdef HOME61 freopen("in", "r", stdin);62 //freopen("out", "w", stdout);63 #endif64 65 fill(colorArr, colorArr + 10, -1);66 cin >> n;67 for (int i = 0; i < n; ++i)68 {69 for (int j = 0; j < n; ++j)70 {71 cin >> imap[i][j];72 }73 }74 Solve(0);75 cout << answer << endl;76 77 78 #ifdef HOME79 cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl;80 _CrtDumpMemoryLeaks();81 #endif82 return 0;83 }
转载于:https://www.cnblogs.com/shijianming/p/5019018.html