Hanoi和全排列

hanoi

#include <bits/stdc++.h>
using namespace std;
void hanoi(int n,char f,char a,char t)
{if(n==1) {printf("Move disk %d from %c to %c\n",n,f,t);return;//要写 }hanoi(n-1,f,t,a);printf("Move disk %d from %c to %c\n",n,f,t);hanoi(n-1,a,f,t);
}
int main()
{int n;while(cin>>n){hanoi(n,'A','C','B');}
}

全排列

#include <bits/stdc++.h>
using namespace std;
int arr[15];int visited[15];
int n;
void print()
{for(int i=0;i<n;i++){cout<<arr[i]<<" ";}cout<<endl;
}
void dfs(int step)
{if(step==n){print();return ;}for(int i=0;i<n;i++){if(!visited[i]){arr[step]=i+1;visited[i]=1; dfs(step+1);visited[i]=0;}}
}
int main()
{while(cin>>n){memset(arr,0,sizeof(arr));memset(visited,0,sizeof(visited));dfs(0);//！n}
}

手机的诱惑

#include <bits/stdc++.h>
using namespace std;
int n,m,T;int tx,ty;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char g[55][55];
int ss=0;
void dfs(int x,int y,int t)
{if(x==tx&&y==ty&&t==T){ss=1;return;}if(t>T) return;//优化增加断点否则回溯又开始了 for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];int nt=t+1;int ttt=T-nt-abs(nx-tx)-abs(ny-ty);if(ttt<0||ttt%2==1) continue;if(nx>=0&&nx<n&&ny>=0&&ny<m){if(g[nx][ny]!='X'){g[nx][ny]='X';dfs(nx,ny,nt);g[nx][ny]='.';}}}
}
int main()
{while(cin>>n>>m>>T){ss=0;int sx,sy;if(n==0&&m==0&&T==0) break;for(int i=0;i<n;i++){scanf("%s",g[i]);}int num=2;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(g[i][j]=='S'){sx=i;sy=j;}if(g[i][j]=='D'){tx=i;ty=j;}if(g[i][j]=='.')num++;}}if(num<T) {cout<<"NO"<<endl;continue;//while不退 }int tt=T-abs(sx-tx)-abs(sy-ty);if(tt<0||tt%2==1){cout<<"NO"<<endl;continue;}g[sx][sy]='X';dfs(sx,sy,0);if(ss) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}