Untitled
3 years ago in Plain Text
//
// main.c
// N-Queens M-Rooks Problem N-Queens M-Rooks Problem N-Queens M-Rooks Problem N-Queens M-Rooks Problem N-Queens M-Rooks Problem N-Queens M-Rooks Problem N-Queens M-Rooks Problem
//
// Created by Angela on 2021/2/3.
//
/*#include<stdio.h>
void place(int row, int n, int m);
int valid(int row, int col, char r);
void display(void);
int position[15];
int role[15];
int N, M, total, count=0;
int main(void)
{
while(scanf("%d %d", &N, &M)!=EOF)
{
count=0;
total=N+M;
place(0, N, M);
printf("%d\n", count);
}
return 0;
}
void place(int row, int n, int m)
{
int i;
if(row==total)
{
display();
}
else
{
for(i=0; i<total; i++)
{
if(valid(row, i, 'Q') && n>0)
{
position[row]=i;
role[row]='Q';
place(row+1, n-1, m);
}
if(valid(row, i, 'R') && m>0)
{
position[row]=i;
role[row]='R';
place(row+1, n, m-1);
}
}
}
}
int valid(int row, int col, char r)
{
int i;
if(r=='Q')
{
for(i=0; i<=row-1; i++)
{
if(position[i]==col || position[i]==col-row+i || position[i]==col+row-i)
return 0;
}
}
if(r=='R')
{
for(i=0; i<=row-1; i++)
{
if(role[i]=='Q')
{
if(position[i]==col || position[i]==col-row+i || position[i]==col+row-i)
return 0;
}
if(role[i]=='R')
{
if(position[i]==col)
return 0;
}
}
}
return 1;
}
void display(void)
{
count++;
// int i;
// for(i=0; i<total; i++)
// {
// printf("%d ", position[i]);
// printf("%c\n", role[i]);
// }
return;
}*/
#include<stdio.h>
void place(int row, int n, int m);
int valid(int row, int col, char r);
void display(void);
int column[10]={0};
int Qright[20]={0};
int Qleft[20]={0};
int Rright[20]={0};
int Rleft[20]={0};
int N, M, total, count=0;
int main(void)
{
while(scanf("%d %d", &N, &M)!=EOF)
{
count=0;
total=N+M;
place(0, N, M);
printf("%d\n", count);
}
return 0;
}
void place(int row, int n, int m)
{
int i;
if(row==total)
{
display();
}
else
{
for(i=0; i<total; i++)
{
if(valid(row, i, 'Q') && n>0)
{
column[i]++;
Qright[row+i]++;
Qleft[i-row+total-1]++;
Rright[row+i]++;
Rleft[i-row+total-1]++;
place(row+1, n-1, m);
column[i]--;
Qright[row+i]--;
Qleft[i-row+total-1]--;
Rright[row+i]--;
Rleft[i-row+total-1]--;
}
if(valid(row, i, 'R') && m>0)
{
column[i]++;
Qright[row+i]++;
Qleft[i-row+total-1]++;
place(row+1, n, m-1);
column[i]--;
Qright[row+i]--;
Qleft[i-row+total-1]--;
}
}
}
}
int valid(int row, int col, char r)
{
if(r=='Q')
{
if(column[col]>0 || Qright[row+col]>0 || Qleft[col-row+total-1]>0)
return 0;
}
if(r=='R')
{
if(column[col]>0 || Rright[row+col]>0 || Rleft[col-row+total-1]>0)
return 0;
}
return 1;
}
void display(void)
{
count++;
return;
}