#include#include#include#include#include#include#include#include#include" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

1301. Cube in Labyrinth

系統 1670 0

http://acm.timus.ru/problem.aspx?space=1&num=1301

一不小心寫了一個三維的spfa? 思路很簡單就是有點繁瑣

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;



const int N=15;

const int INF=0x3f3f3f3f;

//typedef pair<int,int>point;

int dist[N][N][N];

bool in[N][N][N];

int stx,sty,ndx,ndy;

struct node

{

    int u[N],d[N],l[N],r[N];

}mem[N][N];

void init(int n,int m)

{

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

    for(int j=1;j<=m;++j)

    {

        mem[i][j].u[0]=4;

        mem[i][j].d[0]=5;

        mem[i][j].l[0]=3;

        mem[i][j].r[0]=2;

        mem[i][j].u[1]=5;

        mem[i][j].d[1]=4;

        mem[i][j].l[1]=2;

        mem[i][j].r[1]=3;

        mem[i][j].u[2]=2;

        mem[i][j].d[2]=2;

        mem[i][j].l[2]=0;

        mem[i][j].r[2]=1;

        mem[i][j].u[3]=3;

        mem[i][j].d[3]=3;

        mem[i][j].l[3]=1;

        mem[i][j].r[3]=0;

        mem[i][j].u[4]=1;

        mem[i][j].d[4]=0;

        mem[i][j].l[4]=4;

        mem[i][j].r[4]=4;

        mem[i][j].u[5]=0;

        mem[i][j].d[5]=1;

        mem[i][j].l[5]=5;

        mem[i][j].r[5]=5;

    }

    cin>>stx>>sty;

    cin>>ndx>>ndy;

    char a,b,c;

    while(cin>>a)

    {

        if(a=='v'||a=='h')

        c=a;

        else

        {

            cin>>b;

            int x,y;

            x=a-'0';

            y=b-'0';

            for(int i=0;i<6;++i)

            {

                if(c=='v')

                {mem[x][y].d[i]=-1;mem[x+1][y].u[i]=-1;}

                else

                {mem[x][y].r[i]=-1;mem[x][y+1].l[i]=-1;}

            }

        }

    }



}

void solve(int n,int m)

{

    queue<int>qtx,qty,qtk;

    memset(dist,-1,sizeof(dist));

    dist[stx][sty][0]=0;

    in[stx][sty][0]=true;

    qtx.push(stx);

    qty.push(sty);

    qtk.push(0);

    while(!qtx.empty())

    {

        int x=qtx.front();qtx.pop();

        int y=qty.front();qty.pop();

        int k=qtk.front();qtk.pop();

        in[x][y][k]=false;

        if(x-1>=1&&mem[x][y].u[k]!=-1)

        {

            int k1=mem[x][y].u[k];

            if(dist[x-1][y][k1]==-1||dist[x-1][y][k1]>dist[x][y][k]+1)

            {

                dist[x-1][y][k1]=dist[x][y][k]+1;

                if(in[x-1][y][k1]==false)

                {

                    in[x-1][y][k1]=true;

                    qtx.push(x-1);qty.push(y);qtk.push(k1);

                }

            }

        }

        if(x+1<=n&&mem[x][y].d[k]!=-1)

        {

            int k1=mem[x][y].d[k];

            if(dist[x+1][y][k1]==-1||dist[x+1][y][k1]>dist[x][y][k]+1)

            {

                dist[x+1][y][k1]=dist[x][y][k]+1;

                if(in[x+1][y][k1]==false)

                {

                    in[x+1][y][k1]=true;

                    qtx.push(x+1);qty.push(y);qtk.push(k1);

                }

            }

        }

        if(y-1>=1&&mem[x][y].l[k]!=-1)

        {

            int k1=mem[x][y].l[k];

            if(dist[x][y-1][k1]==-1||dist[x][y-1][k1]>dist[x][y][k]+1)

            {

                dist[x][y-1][k1]=dist[x][y][k]+1;

                if(in[x][y-1][k1]==false)

                {

                    in[x][y-1][k1]=true;

                    qtx.push(x);qty.push(y-1);qtk.push(k1);

                }

            }

        }

        if(y+1<=m&&mem[x][y].r[k]!=-1)

        {

            int k1=mem[x][y].r[k];

            if(dist[x][y+1][k1]==-1||dist[x][y+1][k1]>dist[x][y][k]+1)

            {

                dist[x][y+1][k1]=dist[x][y][k]+1;

                if(in[x][y+1][k1]==false)

                {

                    in[x][y+1][k1]=true;

                    qtx.push(x);qty.push(y+1);qtk.push(k1);

                }

            }

        }

    }

}

int main()

{

    //freopen("data.in","r",stdin);

    int n,m;

    while(cin>>n>>m)

    {

        init(n,m);

        solve(n,m);

        if(dist[ndx][ndy][0]==-1)

        cout<<"No solution"<<endl;

        else

        cout<<dist[ndx][ndy][0]<<endl;

    }

}


    

1301. Cube in Labyrinth


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: aaaaa级毛片| 色综合久久九月婷婷色综合 | 国产精品品福利视频 | 国内精品久久久久久久久久影视 | 亚洲国产精品网站久久 | 欧美在线一区二区三区 | 99久久免费精品国产免费 | 91精品一区二区三区久久久久 | 久久午夜精品 | 精品国产日韩久久亚洲 | 麻豆va一区二区三区久久浪 | 网友自拍视频悠悠在线 | 久久频这里精品99香蕉久 | 日韩高清一区 | 久久一级黄色片 | 欧美在线免费视频 | 精品热久国产福利视频 | 色综合天天综合 | 欧美亚洲国产人成aaa | 成人午夜看片在线观看 | 伊人网在线播放 | 日本综合久久 | 亚洲性激情 | 日韩欧免费一区二区三区 | 女人18女人毛片 | 天天弄天天干 | 亚洲综合激情六月婷婷在线观看 | 我想看一级毛片免费的 | 97在线视频免费观看费观看 | 国产亚洲午夜精品 | 亚洲综合在线观看一区www | 欧美性视频一区二区三区 | 一区二区网站 | 中文字幕久久网 | 四虎在线观看网址 | 日本在线一区二区三区 | 97se色在在线视频 | 国产系列在线观看 | 99久久综合九九亚洲 | 欧美真人视频一级毛片 | 亚洲 欧美 中文字幕 |