poj2488骑士之旅

题目大意：国际象棋里面的马，有那么8种跳法，然后题目给出一个棋盘的大小p*q, 求有没有路线可以使得这个马能把整个棋盘的格全部走一遍，有的话按照字典序将第一条路线打印出来。

注意：国际象棋是行是数字，列是字母，按照字典序A1B3....，是需要按照先列后行来处理的。

因为要找一条路径出来，所以考虑深度优先(DFS)

贴一下烂代码（o(╯□╰)o）：

#include<iostream>

#include<string>

using namespace std;

int chess[][];

int path;

bool exist=;

string rec;

void DFS(int y,int x,int szy,int szx)

{

    chess[x][y]=;

    path++;

    rec.push_back(char(y+'A'));

    rec.push_back(char(x+''));

    //cout<<"Beginning:"<<rec<<endl;

    int increx,increy;//,flag=0;

    for(int n=;n<;n++)

    {

        switch(n){

            case :

                increy=-;increx=-;break;

            case :

                increy=-;increx=;break;

            case :

                increy=-;increx=-;break;

            case :

                increy=-;increx=+;break;

            case :

                increy=+;increx=-;break;

            case :

                increy=+;increx=+;break;

            case :

                increy=+;increx=-;break;

            case :

                increy=+;increx=+;break;

        }

        if(y+increy>=szy||y+increy<||x+increx>=szx||x+increx<) continue;

        else if(chess[x+increx][y+increy]==)

        {

            DFS(y+increy,x+increx,szy,szx);

        }

    }

        if(path==szy*szx)

        {

            //cout<<"result:"<<rec<<endl;

            exist=;

        }

        else{

        path--;

        rec.erase(rec.end()-);

        rec.erase(rec.end()-);

        //cout<<"Delete:"<<rec<<endl;

        chess[x][y]=;

        }

}

int main()

{

    int instan,p,q,i,j,k;

    cin>>instan;

    for(i=;i<instan;i++)

    {

        exist=;

        memset(chess,,sizeof(chess));

        cin>>p>>q;

        cout<<"Scenario #"<<i+<<":"<<endl;

        for(j=;j<q;j++)

        {

            for(k=;k<p;k++)

            {

                path=;

                rec.clear();

                //cout<<"Start from "<<k<<" "<<j<<":"<<endl;

                DFS(j,k,q,p);

                if(exist==)

                {

                    cout<<rec<<endl;

                    break;

                }

            }

                if(exist==)

                {

                    break;

                }

        }

        if(exist==) cout<<"impossible"<<endl;

        cout<<endl;

    }

    return ;

}

巴特西

poj2488骑士之旅

最新文章

热门文章