PAT T1022 Werewolf
2024-08-30 06:02:47
暴力搜索加剪枝~
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int a[maxn];
bool visit[maxn];
vector<int> path,tmp;
int N,M,L,cnt=;
void dfs (int v) {
if (tmp.size()==M) {
int liecnt=,liewolf=;
for (int i=;i<=N;i++) {
if (a[i]<&&visit[abs(a[i])]==false) {
liecnt++;
if (visit[i]==true) liewolf++;
}
else if (a[i]>&&visit[abs(a[i])]==true) {
liecnt++;
if (visit[i]==true) liewolf++;
}
}
if (liecnt==L&&liewolf>=&&liewolf<M&&cnt==) path=tmp,cnt++;
return;
}
if (tmp.size()+v<L) return;
v--;
while (v>=) {
visit[v]=true;
tmp.push_back(v);
dfs (v);
visit[v]=false;
tmp.pop_back();
v--;
}
}
int main () {
scanf ("%d %d %d",&N,&M,&L);
for (int i=;i<=N;i++) {
scanf ("%d",&a[i]);
}
dfs (N+);
if (path.size()==) {
printf ("No Solution");
return ;
}
for (int i=;i<path.size();i++) {
if (i!=) printf (" ");
printf ("%d",path[i]);
}
return ;
}
最新文章
- Codeforces558E A Simple Task(线段树)
- 洛谷P2731骑马修栅栏
- comparing-html5-mobile-ui-frameworks
- 2.1.6 用ProtectX实现扫描的反击与追踪
- ZigBee组网原理
- 【转】基于Android Fragment功能的例子
- 【美妙的Python之中的一个】Python简单介绍及环境搭建
- 移动前端制作篇之javascript篇
- django学习之Model(四)MakingQuery
- Windows Server 2016-WinSer2016 Active Directory新增功能
- PhotoShop制作简单的文字动画--多媒体技术与应用
- Myeclipse快速补充返回值快捷键
- python学习之路网络编程篇(第二篇)
- Javascript高级编程学习笔记(94)—— Canvas(11) 合成
- idea的一些设置
- 一个老程序员是如何手写Spring MVC的
- react简书笔记一 环境, git 和 项目 关联
- CSS选择器 + Xpath + 正则表达式整理(有空再整理)
- 工作->;离职->;考研
- mysql系列(3)之 DML语句