大意：
有一张N*N的网格，你每次可以走一步，每格只能走一次，有没有一种方法让走了L步后回到一个距原点1步远的格子？
没有输出Unsuitable device，否则输出Overwhelming power of magic并输出方案。
一开始用DFS 奇偶剪枝了还是TLE,
代码如下：
#include<iostream>
#include<cstring>
#include<cmath>
#define N 110
using namespace std; int n,t,end_i,end_j;
bool visited[N][N],flag,ans;
char map[N][N];
int run[10010][2];
int tem;
int a[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; void DFS(int i,int j,int c)
{
if(flag){ return ;}
if(c>t) return ;
if(i<=0||i>n||j<=0||j>n) {return ;}
if(map[i][j]=='D'&&c==t) {flag=ans=true; return ;}
int temp=abs(i-end_i)+abs(j-end_j);
temp=t-temp-c; //t扣掉还要走的最短步temp 和 已经走过的 c 如果这些步还是奇数直接不满足
if(temp&1) return ;//奇偶剪枝 奇数return
for(int k=0;k<4;k++)
if(!visited[i+a[k][0]][j+a[k][1]]) //开始进行各个方向的探索 记得回溯，取消之前走的状态
{
visited[i+a[k][0]][j+a[k][1]]=true;
DFS(i+a[k][0],j+a[k][1],c+1);
if(flag){cout<<i+a[k][0]<<" "<<j+a[k][1]<<endl;break;}
visited[i+a[k][0]][j+a[k][1]]=false;
}
} int main()
{
int i,j;
while(cin>>n>>t)
{
if(t%2!=0||t>n*n){cout<<"Unsuitable device"<<endl;continue;}
else cout<<"Overwhelming power of magic"<<endl;
cout<<"1 1"<<endl;
memset(visited,0,sizeof(visited)); for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{
map[i][j]='.';
}
}
end_i=2;end_j=1;
map[2][1]='D';
visited[1][1]=1; ans=flag=false; DFS(1,1,1);
// if(ans) cout<<"YES"<<endl;
// else cout<<"NO"<<endl;
}
return 0;
}
后来是找规律做出来的，根据奇偶分类讨论一下；；
代码写的很烂。。
很多复用的没复用。。
#include<iostream>
#include<cstring>
#include<cmath>
#define N 110
using namespace std; int n,t,end_i,end_j;
bool visited[N][N],flag,ans;
char map[N][N];
int run[10010][2];
int tem;
int a[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int main()
{
int i;int xx,yy,kk;
while(cin>>n>>t)
{
if(t%2!=0||t>n*n){cout<<"Unsuitable device"<<endl;continue;}
else cout<<"Overwhelming power of magic"<<endl;
// cout<<"1 1"<<endl;
if(n%2==0){
if(t<=2*n){
for(i=1;i<=t/2;i++){
cout<<1<<" "<<i<<endl;
}
for(i=t/2;i>0;i--){
cout<<2<<" "<<i<<endl;
}
}
else{
kk=t-2*n;
yy=kk/(2*(n-2));
xx=kk%(2*(n-2));
for(i=1;i<=n;i++){
cout<<"1 "<<i<<endl;
}
if(xx!=0){
int w2=n-2;
for( i=2;i<=2+xx/2;i++){
cout<<i<<" "<<n<<endl;
}
for( i=2+xx/2;i>=2;i--){
cout<<i<<" "<<n-1<<endl;
}
while(yy--){ for(i=2;i<=n;i++)
cout<<i<<" "<<w2<<endl;
for(i=n;i>=2;i--)
cout<<i<<" "<<w2-1<<endl;
w2-=2;
}
while(w2!=0){ cout<<"2 "<<w2<<endl;
cout<<"2 "<<w2-1<<endl;
w2-=2;
}
}
else{
int wei;
wei=n;
while(yy--){ for(i=2;i<=n;i++)
cout<<i<<" "<<wei<<endl;
for(i=n;i>=2;i--)
cout<<i<<" "<<wei-1<<endl;
wei-=2;
}
while(wei!=0){ cout<<"2 "<<wei<<endl;
cout<<"2 "<<wei-1<<endl;
wei-=2;
}
}
}
}
else{ if(t<=2*n){
for(i=1;i<=t/2;i++){
cout<<1<<" "<<i<<endl;
}
for(i=t/2;i>0;i--){
cout<<2<<" "<<i<<endl;
}
}
else if(t<=2*n+2*(n-2)){
int er=(t-(2*n))/2;
for(i=1;i<=n;i++){
cout<<1<<" "<<i<<endl;
}
for(i=n;i>=3;i--){
cout<<2<<" "<<i<<endl;
}
for(i=2;i<=2+er;i++){
cout<<i<<" "<<2<<endl;
}
for(i=er+2;i>=2;i--){
cout<<i<<" "<<1<<endl;
} }
else if(t<=(n+n-1+3*(n-2))){
int bb=(t-(2*n+2*(n-2)))/2;
for(i=1;i<=n;i++){
cout<<1<<" "<<i<<endl;
}
for(i=n;i>=3;i--){
cout<<2<<" "<<i<<endl;
}
for(i=3;i<=n;i++){
cout<<i<<" "<<3<<endl;
}
cout<<n<<" "<<2<<endl;
int x=n,y=1;
cout<<x<<" "<<y<<endl;
x--;
cout<<x<<" "<<y<<endl; while(1){
if(x==2&&y==1){break;}
if(bb>0&&y==1&&x%2==0){
y=2;bb--;
cout<<x<<" "<<y<<endl;
}
else if(y==2&&x%2==0){
x--;
cout<<x<<" "<<y<<endl;
}
else if(y==2&&x%2==1){
y=1;cout<<x<<" "<<y<<endl;
}
else if(y==1&&x%2==1){
x--;
cout<<x<<" "<<y<<endl;
}
else if(bb<=0&&y==1&&x%2==0){
x--;
cout<<x<<" "<<y<<endl;
}
}
}
else{
kk=t-(n+n-1+3*(n-2));
yy=kk/(2*(n-2));
xx=kk%(2*(n-2));
for(i=1;i<=n;i++){
cout<<"1 "<<i<<endl;
}
if(xx!=0){
int w21=n-2;
for( i=2;i<=2+xx/2;i++){
cout<<i<<" "<<n<<endl;
}
for( i=2+xx/2;i>=2;i--){
cout<<i<<" "<<n-1<<endl;
}
while(yy--){ for(i=2;i<=n;i++)
cout<<i<<" "<<w21<<endl;
for(i=n;i>=2;i--)
cout<<i<<" "<<w21-1<<endl;
w21-=2;
}
while(w21!=3){ cout<<"2 "<<w21<<endl;
cout<<"2 "<<w21-1<<endl;
w21-=2;
}
}
else{
int wei2;
wei2=n;
while(yy--){ for(i=2;i<=n;i++)
cout<<i<<" "<<wei2<<endl;
for(i=n;i>=2;i--)
cout<<i<<" "<<wei2-1<<endl;
wei2-=2;
}
while(wei2!=3){ cout<<"2 "<<wei2<<endl;
cout<<"2 "<<wei2-1<<endl;
wei2-=2;
}
}
/*
*
*/
for(i=2;i<=n;i++){
cout<<i<<" "<<3<<endl;
}
cout<<n<<" "<<2<<endl;
int x=n,y=1;
cout<<x<<" "<<y<<endl;
x--;
cout<<x<<" "<<y<<endl; while(1){
if(x==2&&y==1){break;}
if(y==1&&x%2==0){
y=2;
cout<<x<<" "<<y<<endl;
}
else if(y==2&&x%2==0){
x--;
cout<<x<<" "<<y<<endl;
}
else if(y==2&&x%2==1){
y=1;cout<<x<<" "<<y<<endl;
}
else if(y==1&&x%2==1){
x--;
cout<<x<<" "<<y<<endl;
} } } } }
return 0;
}
有的队也有用DFS过的T T
#include<iostream>
using namespace std;
int n,l,ans;
void dfs(int x,int y,int z){
if(ans==l) return ;
if(x>n||y>n) return ;
if(z==0){
printf("%d %d\n",x,y);
ans+=2;
dfs(x+1,y,0);
printf("%d %d\n",x,y+1);
if(n%2==x%2) dfs(x,3,1);
}
else if(z==1){
printf("%d %d\n",x,y);
ans+=2;
dfs(x,y+1,1);
printf("%d %d\n",x-1,y);
if(x==3&&y%2==0) dfs(x-2,y,2);
}
else if(z==2){
ans+=2;
printf("%d %d\n",x,y);
printf("%d %d\n",x,y-1);
}
}
int main(){
cin>>n>>l;
if(l%2==1||n*n<l){
printf("Unsuitable device\n");
}
else{
printf("Overwhelming power of magic\n");
printf("1 1\n");
printf("2 1\n");
ans=4;
dfs(3,1,0);
printf("2 2\n");
if(ans!=n) dfs(2,3,1);
printf("1 2\n");
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。