注意条件：不能每放一个棋子，就标记一行和一列，我们直接枚举每一行就可以了。
AC代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
# define ll long long
const int maxn =;
char str[maxn][maxn];
int vis[maxn];
int n,m,num;
void dfs(int u,int cnt)
{
if(cnt==m)
{
num++;
return ;
}
if(u==n)
return ;
for(int i=; i<n; i++)
{
if(!vis[i]&&str[u][i]=='#')
{
vis[i]=;
dfs(u+,cnt+);
vis[i]=;
}
}
dfs(u+,cnt);
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
if(n==-&&m==-)
break;
memset(vis,,sizeof(vis));
num=;
for(int i=; i<n; i++)
{
scanf("%s",str[i]);
}
dfs(,);
printf("%d\n",num);
}
return ;
}
B - Dungeon Master
注意条件：简单三维bfs。
AC代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
# define ll long long
const int maxn =;
char str[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int f[][]= {{,-,,,,},
{,,-,,,},
{,,,,,-}
};
int n,m,k;
int stx,sty,stz;
int edx,edy,edz;
int ans;
bool judge(int x,int y,int z)
{
if(x>=&&x<=n&&y>=&&y<=m&&z>=&&z<=k)
return true;
return false;
}
struct node
{
int x,y,z,step;
node() {}
node(int xx,int yy,int zz,int tt)
{
x=xx,y=yy,z=zz,step=tt;
}
};
void bfs(int x,int y,int z)
{
queue<node>q;
q.push(node(x,y,z,));
vis[x][y][z]=;
while(!q.empty())
{
node top=q.front();
q.pop();
if(top.x==edx&&top.y==edy&&top.z==edz)
{
ans=top.step;
return ;
}
for(int i=; i<; i++)
{
int tx,ty,tz;
tx=top.x+f[][i];
ty=top.y+f[][i];
tz=top.z+f[][i];
if(judge(tx,ty,tz)&&vis[tx][ty][tz]==&&str[tx][ty][tz]!='#')
{
vis[tx][ty][tz]=;
q.push(node(tx,ty,tz,top.step+));
}
}
}
}
int main()
{
while(~scanf("%d %d %d",&n,&m,&k)&&(n+m+k))
{
memset(vis,,sizeof(vis));
ans=-;
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
scanf("%s",str[i][j]+);
for(int l=; l<=k; l++)
{
if(str[i][j][l]=='S')
{
stx=i;
sty=j;
stz=l;
}
if(str[i][j][l]=='E')
{
edx=i;
edy=j;
edz=l;
}
}
}
}
bfs(stx,sty,stz);
if(ans==-)
printf("Trapped!\n");
else
printf("Escaped in %d minute(s).\n",ans);
}
return ;
}
C - Catch That Cow
注意条件：bfs，注意限制条件。
AC代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
# define ll long long
const int maxn =2e5+;
int vis[maxn];
pair<int,int> top;
int bfs(int st,int ed){
queue<pair<int,int> >q;
vis[st]=;
q.push(make_pair(st,));
while(!q.empty()){
top=q.front();
q.pop();
if(top.first==ed){
return top.second;
}
if(top.first+<=ed&&vis[top.first+]==){
vis[top.first+]=;
q.push(make_pair(top.first+,top.second+));
}
if(top.first->=&&vis[top.first-]==){
vis[top.first-]=;
q.push(make_pair(top.first-,top.second+));
}
if(top.first*<=*ed&&vis[top.first*]==){
vis[top.first*]=;
q.push(make_pair(top.first*,top.second+));
}
}
}
int main(){
int n,m;
while(~scanf("%d %d",&n,&m)){
memset(vis,,sizeof(vis));
int ans=bfs(n,m);
printf("%d\n",ans);
}
return ;
}
D - Fliptile
注意条件：直接枚举第一行，然后通过下面的一行调整为他的上一行全为0.找出最小步骤，如果存在多个最小步骤相等。找出字典序最小的（对第一行二进制枚举就可以保证了）
AC代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = ;
int a[maxn][maxn];
int tmp[maxn][maxn];
int ans[maxn][maxn];
int com[maxn][maxn];
int n,m,ti;
void flip(int x,int y){
ti++;
tmp[x][y]^=;
tmp[x+][y]^=;
tmp[x-][y]^=;
tmp[x][y+]^=;
tmp[x][y-]^=;
}
bool judge(int t){
memcpy(tmp,a,sizeof(a));
memset(com,,sizeof(com));
for(int i=m;i>=;i--){
com[][m-i+]=((t&(<<(i-)))>?:);
}
for(int i=;i<=m;i++){
if(com[][i])flip(,i);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(tmp[i-][j])flip(i,j),com[i][j]=;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(tmp[i][j])return false;
}
}
return true;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
int maxstate=(<<m)-;
int maxx=inf;
for(int i=;i<=maxstate;i++){
ti=;
if(judge(i)){
if(maxx>ti){
maxx=ti;
memcpy(ans,com,sizeof(com));
}
}
}
if(maxx==inf){
printf("IMPOSSIBLE\n");
}
else {
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(j==)printf("%d",ans[i][j]);
else printf(" %d",ans[i][j]);
}
printf("\n");
}
}
return ;
}
//溜了，回家玩耍的