003:碁盤問題プログラム設計実習MOOC/プログラム設計とアルゴリズム(二)第08週試験(2020春)

1676 ワード
図説 POJ MOOC
説明
1つの所定の形状の碁盤(形状が不規則である可能性がある)の上に駒を並べ、駒に違いはない.並べ替え時に任意の2つの駒が碁盤の中の同一行または同一列に置かれないことを要求する場合は、所定の形状と大きさの碁盤に対してk個の駒を並べたすべての実行可能な並べ替えスキームCをプログラミングして解いてください.
入力
複数セットのテストデータを入力します.各グループのデータの最初の行は2つの正の整数、n kであり、1つのスペースで区切られ、1つのn*nのマトリクス内に碁盤を記述し、駒を置く数を示す.n<=8,k<=nは−1−1で入力終了を示す.次のn行は、各行にn文字を有する碁盤の形状を示す.空白領域を表します(データは余分な空白行や空白列が現れないことを保証します).
しゅつりょく
各セットのデータに対して、1行の出力が与えられ、配置されたシナリオ数Cが出力される(データ保証C<2^31).
サンプル入力
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

サンプル出力
2
1

問題を解く構想.
0行目から遍歴し、1行目になるごとに、その行に「#」があるかどうかを列ごとに検索し、「#」がある列はまだ駒を見逃されていません.このような「#」を見つけたら、駒をここに置いて、マークをつけて、cnt++を打って、次の行に入ります.ローのすべてのカラムが条件を満たさない場合は、次のローに進みます.境界条件は「行」がテーマから与えられたnを超えていないことである.あるいは,置かれた駒数がkに等しいときに置くことができるシナリオ数ways++である.
AC Code 
#include
#include
#include
//#include
//#include
//#include
//#include
//#include
//#include
//#include
//#include
//#include
using namespace std;

typedef long long ll;
const double PI=acos(-1);
const double EPS=1e-6;
const int INF=0x3f3f3f3f;
const int MAXN=10+10;
int a[MAXN];
int n, k;
int ways=0, cnt=0;
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
bool vx[MAXN], vy[MAXN]; 
void dfs(int x){
	if(vx[x]) return;
	if(cnt==k) {
		++ways;
		return ;
	}
	if(x>=n) return;
	for(int i=0; i

php操作EXCEL(三)Excelの内容を読み取る
Railsチュートリアル備忘録（1章 1.5.1）②