PKU 1321 棋盘问题
http://poj.org/problem?id=1321
n*nのゲームボードがある。
このゲームボードにk個のコマを'#'となっている場所に置きたい。
ただし、一つの行、列にコマは一つまでしか置けない。
何通りの置き方があるかというような問題。
全探索。
時間的にも余裕で通るようです。
翻訳かけたものの意味を把握するほうが手間取りました。
string in[8]; int ans; int n,k; bool use[8]; void dfs(int ro,int rest){ if(rest==0){ ++ans; return; } if(ro>=n)return; rep(i,n){ if(use[i])continue; if(in[ro][i]!='#')continue; use[i]=true; dfs(ro+1,rest-1); use[i]=false; } dfs(ro+1,rest); } main(){ while(cin>>n>>k,~n){ ans=0; rep(i,n)cin>>in[i]; dfs(0,k); cout<<ans<<endl; } }