link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=353#problem/C

题目大意:给出一个棋盘的行列,问一个king想走遍所有的点,是否有可能,可能则输出路径,注意字典序
因为要考虑字典序的问题,所以从第(1,1)开始搜就好了、、
code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int x[]={-2,-2,-1,-1,1,1,2,2};
int y[]={-1,1,-2,2,-2,2,-1,1};/*代表king走的八个方向,不知道为什么换顺序就错了,后来看解题才知道这里有问题,似乎是字典序*/
int visit[30][30];/*记录是否搜过*/
char x_x[30],y_y[30];/*记录行列走过的坐标*/
int p,q;/*p为列,q为行,这里好坑人*/
int flag;/*判断结束的标志*/

void dfs(int total,int xbeg,int ybeg)
{
    int xx,yy,i;
    if(total==p*q)/*一共p*q个点,全部遍历,则说明全部都能走遍*/
    {
        flag=1;
        for(i=0;i<total;i++)
                printf("%c%c",x_x[i],y_y[i]);
        printf("\n");
        return;
    }
    if(flag==1)
			return;/*以前听朱神告我的,判断回溯出去的标志*/
    for(i=0;i<8;i++)
    {
        xx=xbeg+x[i],yy=ybeg+y[i];/*不断更新坐标,遍历八个方向*/
        if(xx>0&&xx<=q&&yy>0&&yy<=p&&visit[xx][yy]==0)
        {
            visit[xx][yy]=1;
            x_x[total]=xx+'A'-1;
            y_y[total]=yy+'0';
            dfs(total+1,xx,yy);/*搜索下一点*/
            visit[xx][yy]=0;/*回溯记得清零*/
        }
    }
}

int main()
{
    int i,t;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        printf("Scenario #%d:\n",i);
        scanf("%d%d",&p,&q);
        flag=0;
        memset(visit,0,sizeof(visit));
        memset(x_x,0,sizeof(x_x));
        memset(y_y,0,sizeof(y_y));
        visit[1][1]=1;
        x_x[0]='A';
        y_y[0]='1';
        dfs(1,1,1);
        if(flag==0)
            printf("impossible\n");
        if(i!=t)
            printf("\n");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation