AcWing 无. dfs
原题链接
中等
作者:
Florentino
,
2021-05-16 15:26:07
,
所有人可见
,
阅读 247
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <cmath>
#include <time.h>
#include <sys/timeb.h>
#include <algorithm>
#include <set>
#include <limits.h>
#include <map>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10;
int a[10][10], ship[10]; //a[i][j]存放点的位置
char x[10][10];
int res = 0;
int n, m;
bool check()
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//if (x[i][j] == 'X' && a[i][j]) return 0;
if (x[i][j] == 'O' && (!a[i][j])) return 0; //O点应该放置,但是没有放置
}
}
return 1;
}
void dfs(int pos) //船从0开始,确定层数为船
{
if (pos == m) { //检查是否遍历完最后一个船,
if (check()) res++; //能够放置,答案数目加一
return;
}
int len = ship[pos]; //len=船的长度
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { //遍历每个点,看这个船可以放置的位置
if (!a[i][j] || x[i][j] == 'X') { //没有被其他船占领,且不是X
//横着放
for (int k = 0; k < len && len + j - 1 < n; k++) {
if (a[i][j + k] || x[i][j + k] == 'X') break;//横着放,利用j
if (k == len - 1) { //遍历到该船的末尾,开始放置
for (int l = 0; l < len; l++) a[i][l + j] = pos + 1; //船的序号
dfs(pos + 1); //遍历下一个船
for (int l = 0; l < len; l++) a[i][l + j] = 0; //回溯
}
}
if (ship[pos] == 1) continue; //船的长度等于1,退出,避免重复计算
//竖着放置
for (int k = 0; k < len && len + i - 1 < n; k++) { //竖着放置
if (a[i + k][j] || x[i + k][j] == 'X') break; //竖着放置,利用i
if (k == len - 1) { //
for (int l = 0; l < len; l++) a[l + i][j] = pos + 1;
dfs(pos + 1);
for (int l = 0; l < len; l++) a[l + i][j] = 0;
}
}
}
}
}
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
scanf("%s", x[i]); //存放原始图
}
for (int i = 0; i < m; i++) {
scanf("%d", &ship[i]);//船的大小
}
dfs(0);
printf("%d\n", res);
return 0;
}