蒟蒻的码风比较繁杂%%%
#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但是为什么跑的这么慢呢