学步园

    题目很简单......但DFS时不断的递归回朔不仅使得时间效率很低...在跑9这个输入时..连系统栈都给爆了..其实仔细的思考..这题是DFS..但是可以不用栈..因为搜到了一个位置..可以很明确的知道若是失败了..我该跳回哪里..并且跳回去我还要尝试搜索哪些数..直接用个while循环就可以了...

Program:

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
int n,s[520][520];
bool used[2][1030][1030];
void search()
{
      int i,x,y;
      s[1][1]=0;
      x=y=1;
      while (y<=n)
      {
            for (i=s[y][x]+1;i<=2*n-1;i++)
            if (!used[0][y][i] && !used[1][x][i] && !used[0][x][i] && !used[1][y][i]) 
            {
                   used[0][y][i]=used[1][x][i]=used[0][x][i]=used[1][y][i]=true;
                   s[y][x]=i;
                   x++; 
                   if (x>n) { y++; x=1; }
                   s[y][x]=0;
                   goto A;
            }
            x--;
            if (!x) { y--; x=n; }
            i=s[y][x];
            used[0][y][i]=used[1][x][i]=used[0][x][i]=used[1][y][i]=false;
            A: ;
      }
      return;
}
int main()
{   
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      memset(used,false,sizeof(used));
      scanf("%d",&n);
      n=(int)pow(double(2),double(n));
      search();
      int i,j;
      for (i=1;i<=n;i++)
      {
            for (j=1;j<=n;j++) printf("%d ",s[i][j]);
            printf("\n");
      }
      return 0;
}