首页 > 代码库 > 梦工厂实验室 蛇形填数 dfs

梦工厂实验室 蛇形填数 dfs

问题 D: 蛇形填数

时间限制: 3 Sec  内存限制: 64 MB
提交: 28  解决: 5
[提交][状态][讨论版]

题目描述

在n*n方阵里填入1,2,...,n*n,要求填成蛇形。例如n=4时方阵为:
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4

输入

直接输入方阵的维数,即n的值。(n<=100)

输出

输出结果是蛇形方阵。

样例输入

3

样例输出

7 8 16 9 25 4 3


一类题型。四个方向dfs,当走不通时,t++改变方向,否则一直往一个方向走。

#include<stdio.h>int a[105][105];int c=1,n,t=0;void dfs(int x,int y){    if(x<1||y<1||x>n||y>n){        t++;        return;    }    if(a[x][y]!=0){        t++;        return;    }    a[x][y]=c;    c++;    while(c<=n*n){    if(t%4==0) dfs(x+1,y);    else if(t%4==1) dfs(x,y-1);    else if(t%4==2) dfs(x-1,y);  //遍历思路    else dfs(x,y+1);    }}int main(){    int i,j;    scanf("%d",&n);    dfs(1,n);    for(i=1;i<=n;i++){        for(j=1;j<=n;j++){            if(j==1) printf("%d",a[i][j]);            else printf(" %d",a[i][j]);        }        printf("\n");    }    return 0;} /**************************************************************    Problem: 1541    User: 2016207228    Language: C    Result: 正确    Time:1 ms    Memory:1312 kb****************************************************************/

 

梦工厂实验室 蛇形填数 dfs