A - 棋盘问题
#include <bits/stdc++.h>
using namespace std;
int ans=0;//最终方案数
int h0,qi0;
char map0[10][10];
int book[10];
void dfs(int h1,int qi1)//h1是变化的行
{
if(qi1==0||h1==h0){ if (qi1== 0)ans++; return ;}//如果棋下完了或棋下到了最后一行，则说明为最底层，则返回上一层
//ans是全局，可以被反馈给每一层
else//下棋
{ for(int i=0;i<h0;i++)
{ if(book[i]==0&&map0[h1][i]=='#')
{ book[i]=1;//放置棋子并标记
dfs(h1+1,qi1-1);//向下一行，棋子少1个
book[i]=0;//撤销标记，拿走棋子,以应对世界线分支
}
}
dfs(h1+1,qi1);//在回朔流中重放棋子，展开分支世界线
return ;//支路世界线的结束与反馈
}
}
int main()
{
while(cin>>h0>>qi0 && !(h0==-1&&qi0==-1))
{
for(int i=0;i<h0;i++)
{ for(int j=0;j<h0;j++)
{
cin>>map0[i][j];
}
}
dfs(0,qi0);//最开始从第0行开始，到h0-1行结束
cout<<ans<<endl;
ans=0;memset(book, 0, sizeof(book));//重置
}
}
B - Perket
#include<bits/stdc++.h>
using namespace std;
int n,s = 1, b = 0;
struct A{
int s = 1, b = 0;
}num[11];
int sum =1e9;
void dfs(int a,int s,int b){
if(a==n){
if(s == 1&& b == 0){
return;
}
sum = min(sum ,abs(s-b));
return;
}
dfs(a+1,s*num[a].s,b+num[a].b);
dfs(a+1,s,b);
}
int main()
{
cin>>n;
for(int i = 0; i < n+1; i ++){
cin>>num[i].s>>num[i].b;
}
dfs(0,1,0);
cout<<sum;
return 0;
}
C - 全排列
#include<bits/stdc++.h>
using namespace std;
char a[1000];
int main()
{ cin>>a;
do{
printf("%s\n",a);
}while(next_permutation(a,a+strlen(a)));
}
D - 自然数拆分
#include<bits/stdc++.h>
using namespace std;
int n,cnt=1, m;;
int p[1000]={1};
void cout1(int a)
{ cout<<n<<"=";
for(int i=1; i<a; i++)cout<<p[i]<<"+";
cout<<p[a]<<endl;
}
void dfs(int a){
for(int i=p[a-1]; i<=m; i++){
if(i==n) continue;
p[a]=i;
m-=i;
if(m==0) cout1(a);
else dfs(a+1);
m+=i;
}
}
int main()
{
cin>>n;m=n;
dfs(1);
return 0;
}
E - Prime Ring Problem
#include<bits/stdc++.h>
using namespace std;
int n,cnt=1, m;;
int p[1000]={1};
void cout1(int a)
{ cout<<n<<"=";
for(int i=1; i<a; i++)cout<<p[i]<<"+";
cout<<p[a]<<endl;
}
void dfs(int a){
for(int i=p[a-1]; i<=m; i++){
if(i==n) continue;
p[a]=i;
m-=i;
if(m==0) cout1(a);
else dfs(a+1);
m+=i;
}
}
int main()
{
cin>>n;m=n;
dfs(1);
return 0;
}
F - Red and Black
#include <bits/stdc++.h>
using namespace std;
char a[24][24];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int w,h;
int sum = 0;
void dfs(int p,int q){
a[p][q] = '#';
sum++;
int nx,ny;
for(int i = 0;i < 4;i++){
nx = p + dx[i];
ny = q + dy[i];
if(a[nx][ny] == '.' && p >= 0 && q >= 0 && nx < h && ny < w){
dfs(nx,ny);
}
}
return ;
}
int main(){
while(scanf("%d%d",&w,&h) != EOF){
int n,m;
if(w == h && w == 0){
break;
}
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
cin>>a[i][j];
}
}
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(a[i][j] == '@'){
dfs(i, j);
}
}
}
printf("%d\n",sum);
sum = 0;
}
return 0;
}
G - Knight Moves
#include<bits/stdc++.h>
using namespace std;
const int len=302;
struct horse{
int x;
int y;
int step;
};
bool Visit[len][len];
const int way[8][2]={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
void bfs(int s1,int e1,int s2,int e2,int lenth){
queue<horse> q;
horse start,now,next;
start.x=s1;
start.y=e1;
start.step=0;
Visit[start.x][start.y]=true;
q.push(start);
while(!q.empty()){
now=q.front();
q.pop();
if(now.x==s2&&now.y==e2){
cout<<now.step<<endl;
return;
}
for(int i=0;i<8;i++){
next.x=now.x+way[i][0];
next.y=now.y+way[i][1];
if(next.x>=0&&next.x<lenth&&next.y>=0&&next.y<lenth&&!Visit[next.x][next.y]){
next.step=now.step+1;
q.push(next);
Visit[next.x][next.y]=true;
}
}
}
}
int main()
{
int n;
cin>>n;
int l;
int x1,x2,y1,y2;
for(int i=0;i<n;i++){
cin>>l;
cin>>x1>>y1;
cin>>x2>>y2;
memset(Visit,false,sizeof(Visit));
bfs(x1,y1,x2,y2,l);
}
return 0;
}
H - Oil Deposits
#include<stdio.h>
#include<string.h>
int a,b,sum;
char str[100][100];
int c[8][2]={0,1,0,-1,1,0,-1,0,-1,-1,1,1,-1,1,1,-1};
void dfs(int i,int j)
{
int k;
for(k=0;k<8;k++){
int dfsi=i+c[k][0];
int dfsj=j+c[k][1];
if(dfsi<0||dfsj<0||dfsi>=a||dfsj>=b||str[dfsi][dfsj]=='*') continue;
str[dfsi][dfsj]='*';
dfs(dfsi,dfsj);
}
}
int main()
{
while(~scanf("%d %d",&a,&b)){
int i,j;
sum=0;
if(a==0) break;
for(i=0;i<a;i++)
{
scanf("%s",str[i]);
}
for(i=0;i<a;i++)
{
for(j=0;j<b;j++){
if(str[i][j]=='@'){
str[i][j]='*';
dfs(i,j);
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
I - Lake Counting
#include<bits/stdc++.h>
using namespace std;
char a[1000][1000];
int n,m;
void dfs(int x,int y){
int i,j,b,c;
for(i=-1;i<=1;i++){
for(j=-1;j<=1;j++){
b=i+x;
c=y+j;
if(b>=0&&b<n&&y>=0&&y<m&&a[b][c]=='W'){
a[b][c]='.';
dfs(b,c);
}
}
}
}
int main()
{
int i,j,cnt=0;
while(scanf("%d %d",&n,&m)!=EOF){
memset(a,'0',sizeof(a));
cnt=0;
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);
for(i=0;i<=n-1;i++){
for(j=0;j<=m-1;j++){
if(a[i][j]=='W'){
cnt++;
dfs(i,j);
}
}
}
printf("%d\n",cnt);
}
}
J - 二叉树先序遍历
#include<bits/stdc++.h>
using namespace std;
struct p{
int l;
int r;
}t[100010];
void dfs(int x){
if(x==0)
return;
cout<<x<<endl;//第1步
dfs(t[x].l);//第2步
dfs(t[x].r);//第3步
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>t[i].l>>t[i].r;//依次读入左右节点
dfs(1);
return 0;
}
K - 迷宫（一）
#include<bits/stdc++.h>
using namespace std;
int rule[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //右->下->左->上
char map0[12][12];
int n,m;
int f = 0;
int book[12][12];
void dfs(int x1, int y1) {
if (map0[x1][y1]=='T'){f = 1; return;}
else
{
for (int i=0;i<=3;i++)
{
if((x1+rule[i][0]>=0&&x1+rule[i][0]<n&&y1+rule[i][1]>=0&&y1+rule[i][1]<m)&&map0[x1+rule[i][0]][y1+rule[i][1]]!='*'&&book[x1+rule[i][0]][y1+rule[i][1]]==0)
{ book[x1+rule[i][0]][y1+rule[i][1]]=1;
dfs(x1+rule[i][0], y1+rule[i][1]);
}
}
}
}
int main()
{ int x0,y0;
cin>>n>>m;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{ cin>>map0[i][j];
if (map0[i][j]=='S')
{
x0=i;
y0=j;
}
}
}//扫描地图同时记录出口位置
dfs(x0,y0);
if(f==1)cout<<"yes";
else cout<<"no";
}
L - 马走日
#include<bits/stdc++.h>
using namespace std;
int f[21][22],n,m,t;
int xx[10]={-2,-2,-1,1,2,2,1,-1};//用两个数组表示方向，也就是坐标变化
int yy[10]={-1,1,2,2,1,-1,-2,-2};
int x,y,ans;
void dfs(int a,int b){
bool p=true;
for(int i=1;i<=n;i++){//判断是不是走过了所有点
for(int j=1;j<=m;j++){
if(f[i][j]==0){
p=false;
break;
}
}
}
if(p==true){
ans++;
return;
}
for(int i=0;i<=7;i++){
int l=a+xx[i];
int k=b+yy[i];
if(f[l][k]==1)
continue;
if(l>0&&l<=n&&k>0&&k<=m){
f[l][k]=1;
dfs(l,k);
f[l][k]=0;
}
}
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d %d %d %d",&n,&m,&x,&y);
x++;
y++;
memset(f,0,sizeof(f));
f[x][y]=1;
ans=0;
dfs(x,y);
printf("%d\n",ans);
}
return 0;
}
M - 八皇后问题
#include<bits/stdc++.h>
using namespace std;
const int n = 8;
int tmp, ans;
int x[10];
int chess[10][10];
bool no(int r, int c) {//判断两个皇后的坐标是否冲突
for (int i = 0; i < r; i++) {
if (x[i] == c || abs(r - i) == abs(c - x[i]))
return false;
}
return true;
}
void queen(int k) {
if (k == n) {
ans = max(ans, tmp);//找所有情况的八皇后的最大权值和
return;
}
for (int i = 0; i < n; i++) {
if (no(k, i)) {
x[k] = i;//dfs前做好标记
tmp += chess[k][i];
queen(k + 1);
x[k] = 0;//dfs后删除标记
tmp -= chess[k][i];
}
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
tmp = ans = 0;
memset(x, 0, sizeof(x));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
scanf("%d", &chess[i][j]);
}
queen(0);
printf("%d\n", ans);
}
return 0;
}
N - 选数
#include<bits/stdc++.h>
using namespace std;
int ans,n,k,a[50],i;
bool check(int a)
{
int i;
if(a<2)
return false;
for(i=2;i<=sqrt(a);i++)
if(a%i==0)
return false;
return true;
}
void dfs(int num,int i,int sum){
if(num==k){//输入的k个数之和是素数
if(check(sum))
++ans;
return;
}
for(i;i<=n;i++)
dfs(num+1,i+1,sum+a[i]);//向下一个数搜索
}
int main()
{
cin>>n>>k;
for(i=1;i<=n;i++)
cin>>a[i];
dfs(0,1,0);
cout<<ans;
return 0;
}
O - 打开灯泡 Switch the Lamp On
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=510;
const int dxy1[4][2]= {{1,1},{-1,-1},{1,-1},{-1,1}},dxy2[4][2]= {{1,1},{0,0},{1,0},{0,1}};
struct node
{
int x,y;
};
int t,n,m,ans=1e8,dis[N][N];
char s[N][N];
bool vis[N][N];
deque<node> q;
int check(int x,int y)
{
return x>=0 && x<=n && y>=0 && y<=m;
}
void bfs()
{
vis[0][0]=1;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q.push_front(node {0,0});
dis[0][0]=0;
while(q.size())
{
node now=q.front();
q.pop_front();
fir(i,0,3)
{
int tx=now.x+dxy1[i][0],t1=now.x+dxy2[i][0];
int ty=now.y+dxy1[i][1],t2=now.y+dxy2[i][1];
int tt=(s[t1][t2] != (i<=1? '\\':'/'));
if(check(tx,ty) && dis[tx][ty]>dis[now.x][now.y]+tt)
{
dis[tx][ty]=dis[now.x][now.y]+tt;
if(tt)
q.push_back(node {tx,ty});
else
q.push_front(node {tx,ty});
}
}
}
}
int main()
{
cin>>n>>m;
fir(i,1,n)
fir(j,1,m)
cin>>s[i][j];
bfs();
if(dis[n][m]<1e8)
cout<<dis[n][m]<<endl;
else
cout<<"NO SOLUTION"<<endl;
return 0;
}
