#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條評論
主站蜘蛛池模板: 午夜91| 男女羞羞免费视频 | 九九精品国产兔费观看久久 | 天天操天天射天天色 | 四虎永久免费 | 九九九九精品视频在线播放 | 日韩黄a级成人毛片 | 狠狠色噜噜狠狠狠狠2021天天 | 欧洲亚洲综合一区二区三区 | 99热这里只有精品在线观看 | 日韩综合图区 | 99爱在线精品视频网站 | 色偷偷亚洲精品一区二区 | 99在线观看免费视频 | 这里只有精品在线播放 | 国产中的精品一区的 | 婷婷在线视频国产综合 | 99久久精品国产片久人 | 中文欧美日韩 | 欧美区视频 | 岛国片欧美一级毛片 | 热99re久久国超精品首页 | 91亚洲免费 | 久草精品视频在线观看 | 99999久爱视频在线观看 | 精品久久久久久久中文字幕 | 天天射天天干天天插 | 午夜网站在线观看免费网址免费 | 一本久久a久久精品vr综合 | 欧美网站黄 | 国产欧美在线观看视频 | 亚洲国产精品一区二区久久hs | 欧美成人精品高清在线播放 | 自拍偷拍一区 | 东北一级毛片 | 狠久久| 日本午夜大片a在线观看 | 天天干视频在线 | 久久久夜色精品国产噜噜 | 欧美xxxx8888视频| 亚洲精品一区henhen色 |