学步园

//DFS深度优先搜索/回溯法/八皇后类型题<br /> #include<iostream><br /> using namespace std;<br /> char map[9][9];<br /> int vis[9];//vis数组标记当前列是否已有其他棋从而提高效率<br /> int n,c,tot;<br /> void dfs(int l,int cnt)//cnt当前还有多少棋子要摆放<br /> {<br /> if(cnt == 0) //递归边界，所有棋子已合理摆放完毕<br /> {<br /> tot++;//解个数<br /> return;<br /> }<br /> if(n-l+1 < cnt) return;//剩余行数不足够摆放剩余棋子，则跳出<br /> else dfs(l+1,cnt);//若足够，则空掉当前行继续递归</p> <p> if(cnt > 0)<br /> {<br /> for(int i = 1;i <= n;++i)<br /> {<br /> if(map[l][i] == '.')continue;<br /> else<br /> {<br /> if(!vis[i])//当前列还没有摆放过棋子<br /> {<br /> vis[i] = 1;<br /> dfs(l+1,--cnt);<br /> vis[i] = 0;//DFS出口恢复修改值<br /> ++cnt;//DFS出口恢复修改值<br /> }<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> while(cin >> n >> c)<br /> {<br /> if(n == -1)break;<br /> tot = 0;<br /> for(int i = 1;i <= n;++i)<br /> for(int j = 1;j <= n;++j)<br /> cin >> map[i][j];<br /> dfs(1,c);<br /> cout << tot << endl;<br /> }<br /> return 0;<br /> }