诡异的楼梯
大多数都是用优先队列写的。以前不会优先队列 - - 写的好蛋疼。
还是在学长帮我改了下才AC的。。。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MAX 30
int m,n;
int i,j,x,y,x1,y1;
int fx[] = {1,-1,0,0};
int fy[] = {0,0,1,-1};
char map[MAX][MAX];
int step[MAX][MAX];
struct Point{
int x,y,t;
}que[50000];
void bfs(){
int head,tail;
Point now,next;
que[head = tail = 0] = (Point){x,y,0};
step[x][y] = 0;
while (head <= tail){
now = que[head++];
step[now.x][now.y]=now.t;
if (map[now.x][now.y]=='T'){
printf("%d\n",now.t);
return ;
}
for (i = 0;i < 4;i++){
next = (Point){now.x + fx[i],now.y + fy[i],now.t+1};
if (next.x < 0 || next.x >= m || next.y < 0 || next.y >= n || step[next.x][next.y] != -1)
continue;
if (map[next.x][next.y] == '.' || map[next.x][next.y]=='T'){
step[next.x][next.y] = step[now.x][now.y] + 1;
que[++tail] = next;
continue;
}
if (map[next.x][next.y] == '|'){
next.x+=fx[i];
next.y+=fy[i];
if (next.x < 0 || next.x >= m || next.y < 0 || next.y >= n || step[next.x][next.y] != -1)continue;
if (map[next.x][next.y] != '.' && map[next.x][next.y]!='T')continue;
if ((step[now.x][now.y] ) % 2 == 1 && (i == 2 || i == 3) || (step[now.x][now.y] ) %2 == 0 && (i == 0 || i == 1))//横着走
{
step[next.x][next.y] = step[now.x][now.y] + 1;
que[++tail] = next;
continue;
}
que[++tail] = (Point){
now.x,now.y,now.t + 1
};
continue;
}
if (map[next.x][next.y] == '-'){
next.x+=fx[i];
next.y+=fy[i];
if (next.x < 0 || next.x >= m || next.y < 0 || next.y >= n || step[next.x][next.y] != -1)continue;
if (map[next.x][next.y] != '.' && map[next.x][next.y]!='T')continue;
if ((step[now.x][now.y] ) %2 == 0 && (i == 2 || i == 3) || (step[now.x][now.y] ) %2 == 1 && (i == 1 || i == 0))//横着走
{
step[next.x][next.y] = step[now.x][now.y] + 1;
que[++tail] = next;
continue;
}
que[++tail] = (Point){now.x,now.y,now.t + 1};
continue;
}
}
}
}
int main(){
while (~scanf("%d%d",&m,&n)){
for (i = 0;i < m;i++){
scanf("%s",map[i]);
for (j = 0;j < n;j++){
step[i][j] = -1;
if (map[i][j] == 'S'){
x = i;
y = j;
}
if (map[i][j] == 'T'){
x1 = i;
y1 = j;
}
}
}
bfs();
continue;
for (i = 0;i < n;i++)
{
for (j = 0;j < m;j++)
printf("%-3d ",step[i][j]);
printf("\n");
}
}
return 0;
}
/*
5 5
**...
**.*.
..|T.
.*.**
S....
5 5
**...
**.*.
..|*T
.*.**
S....
5 5
**...
**.*.
..|..
.*.**
S*..T
*/