在中國(guó)象棋中，馬是走日字的。一個(gè)馬的管轄范圍指的是當(dāng)前位置以及一步之內(nèi)能走到的位置，如果一匹馬的某個(gè)方向被蹩馬腳，它就不能往這個(gè)方向跳了。自行腦補(bǔ)
那么問題來了，在一個(gè)?n*m 的棋盤內(nèi)，如何用最少的馬管轄住所有?n*m 個(gè)格子。比如?n=m=3 時(shí)，最少要用?5?只馬才能管轄所有棋盤，一種可能的方案如下：藍(lán)橋
?
枚舉子集tql
建立坐標(biāo)系的時(shí)候不是很順手
多敲幾次

#include <bits/stdc++.h> using namespace std; int mp[100][100]; int vis[100][100]; int head[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; int dirx[4][2]={-1,1, -1,1, -2,-2, 2,2}; int diry[4][2]={2,2, -2,-2, -1,1, 1,-1}; int n, m; bool in(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } int main() {freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&m)!=EOF){memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));int r = n * m;int minx = r + r, ans = 0;for (int s = 0; s < 1 << r; s++) {memset(vis, 0, sizeof vis);int cnt = 0;for (int i = 0; i < r; i++) {if (s >> i & 1) {mp[i / n][i % m] = 1;cnt++;} else {mp[i / n][i % m] = 0;}} // for(int i=0;i<n;++i){ // for(int j=0;j<m;++j){ // cout << mp[i][j] << ' '; // } // cout << endl; // } // cout << "***********************************" << endl;if (cnt > minx) continue;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mp[i][j] == 0) continue;vis[i][j] = 1;for (int k = 0; k < 4; k++) {int x = i + head[k][0], y = j + head[k][1];if (in(x, y) && mp[x][y] == 0) {for (int u = 0; u < 2; u++) {int tx = i + dirx[k][u];int ty = j + diry[k][u];if (in(tx, ty)) {vis[tx][ty] = 1;}}}}}}int ok = 1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (vis[i][j] == 0) {ok = 0;break;}}}if (ok) {if (cnt < minx) {minx = cnt;ans = 1;} else if (cnt == minx) {ans++;}}}printf("%d %d\n", minx, ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的马的管辖 枚举子集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。