题目链接：点击打开链接
题目大意：
1.“输出若干行，第i行表示放i个车的方案数”，这句话意思并不是n有几行，就输出几行，而是有结果就输出。举个例子，假如n = 8，最多可能放64个棋子（其实也没那么多）那么你应该输出从放1个棋子到放64个棋子的每个结果。可是样例中只输出三行，让我误以为输出结果就是从放1个到n个棋子的结果。其实样例的那种情况是凑巧，因为如果放4个以上的棋子是不存在的情况。
2.如果某个方案数为0，就不输出结果。例如题目样例中的情况，当这个棋盘放4个棋子时是不可以的，同理5、6、7、8...都没有合理的方案。
3.推荐在看解析代码之前稍微有【八皇后】相关问题的思想，八皇后解题链接。
解题思路：以布满最大值点的个数为主线，然后分别在去往布满的路上顺便记录每次 i 个点时的情况++。
AC 代码
#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int N=10; int mp[N][N],vis[N][N],ans[N*N]; // 检测冲突 int judge(int x,int y,int n) { int leX,rgX,upY,dwY; leX=rgX=x; upY=dwY=y; // （为了遇见你：洞）且最后坐标正好在洞中 for(;leX>=0&&mp[leX][y]!=0;leX--); // 往上 for(;rgX<n&&mp[rgX][y]!=0;rgX++); // 往下 for(;upY>=0&&mp[x][upY]!=0;upY--); // 往左 for(;dwY<n&&mp[x][dwY]!=0;dwY++); // 往右 // 检查：洞与洞之间，或洞与障碍物之间是否存在已访问点 for(int i=leX+1;i<rgX;i++) // 需要+1，否则就在洞中，显然多此一举 if(vis[i][y]==1&&i!=x) return 0; for(int j=upY+1;j<dwY;j++) // 同上 if(vis[x][j]==1&&j!=y) return 0; return 1; } void dfs(int x,int y,int n,int cur) { if(cur<=n*n) // 一开始的cur==0没用的，只是一根导火线罢了 ans[cur]++; for(int i=x;i<n;i++) // 先从当前行往后判断，判断完后再从下一行，从 j==0 开始 { int c; if(i==x) c=y; // 是否当前行，若是则继续向当前行的后面执行 else c=0; for(int j=c;j<n;j++) { if(vis[i][j]==1||mp[i][j]==0) // 已访问的点 或 是个洞 continue; if(judge(i,j,n)) { vis[i][j]=1; // 可放置 dfs(i,j+1,n,cur+1); // 这里是j+1，而不是j（当然也可以，不过多此一举） vis[i][j]=0; // 回溯 } } } } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&mp[i][j]); mem(vis,0); // 以布满最大值点的个数为主线，然后分别在去往布满的路上顺便记录每次 i 个点时的情况++。 dfs(0,0,n,0); // 一次dfs就行，把dfs的过程中每次结果保存起来(ans[]) for(int i=1;i<=n*n;i++) { if(ans[i]!=0) printf("%d\n",ans[i]); else break; } } return 0; }
