一个普通的bfs 如果不看样例和input的解释...
四个0真是神样例 又被input误导 以为每个点都按顺序有标号 传送门的终点给的是一个点的标号
然后结果是什么呢？无尽的runtime error...持续了半个训练赛的runtime error..
然后其实传送门的终点给的是坐标 莫忘-1
然后vector莫忘清空
然后当bfs开始扫传送门的时候莫忘 b是不停在变的(至少在我写的程序中是) 所以for循环中v[][]括号中的应该是从队列中取出来的node的坐标
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<vector>
#include<queue>
using namespace std;
char ma[505][505];
struct node
{
int x,y,t;
};
int n,m;
vector <node >v[505][505];
bool vis[505][505];
bool check(node a)
{
if(a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&ma[a.x][a.y]!='#'&&vis[a.x][a.y]==true)
return true;
return false;
}
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int sx,sy;
void bfs()
{
node te;
te.x=sx;
te.y=sy;
te.t=0;
queue<node >q;
q.push(te);
vis[te.x][te.y]=false;
node b;
node c;
while(!q.empty())
{
te=q.front();
q.pop();
if(ma[te.x][te.y]=='t')
{
printf("%d\n",te.t);
return ;
}
for(int i=0;i<5;i++)
{
if(i<4)
{
b=te;
b.t++;
b.x+=dx[i];
b.y+=dy[i];
if(check(b))
{
q.push(b);
vis[b.x][b.y]=false;
}
}
else
{
b=te;
b.t++;
node f=b;
for(int k=0;k<v[b.x][b.y].size();k++)
{
c=v[b.x][b.y][k];
f=b;
f.x=c.x;
f.y=c.y;
if(check(f))
{
q.push(f);
vis[f.x][f.y]=false;
}
}
}
}
}
}
int main(){
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
for(int k=0;k<m;k++)
{
vis[i][k]=true;
v[i][k].clear();
}
for(int i=0;i<n;i++)
{
scanf("%s",ma[i]);
}
for(int i=0;i<n;i++)
{
for(int k=0;k<m;k++)
{
int z;
scanf("%d",&z);
for(int j=1;j<=z;j++)
{
int x,y;
scanf("%d%d",&x,&y);
node te;
te.x=x-1;
te.y=y-1;
v[i][k].push_back(te);
}
}
}
bool shengshi=false;
for(int i=0;i<n;i++)
{
for(int k=0;k<m;k++)
{
if(ma[i][k]=='s')
{
shengshi=true;
sx=i;
sy=k;
break;
}
}
if(shengshi)
break;
}
bfs();
}
}