AC但是耗时为什么这么长
查看原帖
AC但是耗时为什么这么长
118238
A_L_1_S_楼主2024/3/12 16:16

蒟蒻的码风比较繁杂%%%

#include <bits/stdc++.h>
using namespace std ;
int n,m;
int stx,sty,edx,edy ;
char c ;
int mp[60][60] ;
bool vis[60][60] ;
bool v[60][60][5] ;
int tl[5] = {0,4,1,2,3} ;
int tr[5] = {0,2,3,4,1} ;
 
struct node{
    int x ;
    int y ;
    int direction ;
    int t ;
};

struct cmp{
    bool operator()(node a,node b) {
        return a.t > b.t ;
    }
};

inline bool judge(node a)
{
    if(mp[a.x][a.y])
        return 1 ;
    return 0 ;
}
//判断障碍

inline bool pend(node a)
{
    if(vis[a.x][a.y]||a.x<2||a.x>n||a.y<2||a.y>m)
        return 1 ;
    return 0 ;
}
//判断越界和重复

int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            int a ;
            cin >> a ;
            if(a)
            {
                mp[i][j] = 1 ;
                mp[i+1][j] = 1 ;
                mp[i][j+1] = 1 ;
                mp[i+1][j+1] = 1 ;
            }
        }
    }
    cin >> stx >> sty >> edx >> edy >> c ;
    stx = stx + 1 ;
    sty = sty + 1 ;
    edx = edx + 1 ;
    edy = edy + 1 ;
    priority_queue<node,vector<node>,cmp> que ;
    node now ;
    now.x = stx ;
    now.y = sty ;
    now.t = 0 ;
    switch(c)
    {
    case 'N' :
        now.direction = 1 ;
        break;
    case 'E' :
        now.direction = 2 ;
        break ;
    case 'S' :
        now.direction = 3 ;
        break ;
    case 'W' :
        now.direction = 4 ;
        break ;
    default:
        break;
    }
    que.push(now) ;
    int ans = -1 ;
    while(!que.empty())
    {
        now = que.top() ;
        que.pop() ;
        if(now.x == edx && now.y == edy)
        {
            ans = now.t ;
            break ;
        }
        vis[now.x][now.y] = 1 ;
        v[now.x][now.y][now.direction] = 1 ;
        node nxt=now ;
        switch(now.direction)
        {
            case 1 :
            for(int i = 1 ; i <= 3 ; i++)
            {
                nxt.x = now.x - i ;
                if(judge(nxt)) break ;
                if(pend(nxt)) continue ;
                nxt.t = now.t + 1 ;
                que.push(nxt) ;
            }
            break ;
            case 2 :
            for(int i = 1 ; i <= 3 ; i++)
            {
                nxt.y = now.y + i ;
                if(judge(nxt)) break ;
                if(pend(nxt)) continue ;
                nxt.t = now.t + 1 ;
                que.push(nxt) ;
            }
            break ;
            case 3 :
            for(int i = 1 ; i <= 3 ; i++)
            {
                nxt.x = now.x + i ;
                if(judge(nxt)) break ;
                if(pend(nxt)) continue ;
                nxt.t = now.t + 1 ;
                que.push(nxt) ;
            }
            break ;
            case 4 :
            for(int i = 1 ; i <= 3 ; i++)
            {
                nxt.y = now.y - i ;
                if(judge(nxt)) break ;
                if(pend(nxt)) continue ;
                nxt.t = now.t + 1 ;
                que.push(nxt) ;
            }
            break ;
            default :
            break ;
        }
        nxt = now ;
        nxt.direction = tl[now.direction] ;
        nxt.t = now.t + 1 ;
        if(!v[nxt.x][nxt.y][nxt.direction])
            que.push(nxt) ;
        nxt = now ;
        nxt.direction = tr[now.direction] ;
        nxt.t = now.t + 1 ;
        if(!v[nxt.x][nxt.y][nxt.direction])
            que.push(nxt) ;
    }
    cout << ans << endl ;
}

看了下测评记录要340ms但是别人的AC记录好像普遍都是60ms左右没有超过100ms的,虽然也能A但是为什么跑的这么慢呢

2024/3/12 16:16
加载中...