xiaolou @ 2018-10-04 13:14:35
https://www.luogu.org/record/show?rid=11467018//23333222
#include <bits/stdc++.h>
using namespace std;
char m[1005][1005];
bool vis[1005][1005];
struct Node
{
int x,y;
int step;
};
int movex[4]={0,0,1,-1};
int movey[4]={1,-1,0,0};
queue <Node> q;
int n;
int bfs(int x,int y,int endx,int endy)
{
Node now;
now.x=x;
now.y=y;
now.step=0;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<4;i++)
{
Node next;
next.x=now.x+movex[i];
next.y=now.y+movey[i];
if(next.x>=1&&next.y>=1||next.x<=n&&next.y<=n&&vis[next.x][next.y]==false&&m[next.x][next.y]=='0')
{
if(next.x==endx&&next.y==endy)
return next.step;
vis[next.x][next.y]=true;
next.step=now.step+1;
q.push(next);
}
}
}
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> m[i][j];
int x,y;
cin >> x >> y;
int endx,endy;
cin >> endx >> endy;
cout << bfs(x,y,endx,endy);
return 0;
}
by NaCly_Fish @ 2018-10-04 13:35:03
把bool换成bitset试试
by NaCly_Fish @ 2018-10-04 13:35:42
@NaCly_Fish 内存可以少
by xiaolou @ 2018-10-04 13:36:38
@NaCly_Fish 怎么改。。。我不会。。。
by NaCly_Fish @ 2018-10-04 13:38:41
@xiaolou 搞一个存bitset的数组;只需要
bitset<1003> b;
就可以创建一个名为b的bitset,可以下标查询,每一项存的都是一个bit,所以可以当作bool使
by NaCly_Fish @ 2018-10-04 13:39:01
@NaCly_Fish 那个1003代表的是bitset的大小
by NaCly_Fish @ 2018-10-04 13:41:06
啊对了,没看见,把
、if(next.x>=1&&next.y>=1||next.x<=n&&next.y<=n&&vis[next.x][next.y]==false&&m[next.x][next.y]=='0') 中的||改成&&
by xiaolou @ 2018-10-04 13:41:11
那要是二位的呢。。。 @NaCly_Fish
by xiaolou @ 2018-10-04 13:42:56
二维。。。
by NaCly_Fish @ 2018-10-04 13:44:29
@xiaolou 你说哪个二位的。。。我太弱看不懂您什么意思
by eros1on @ 2018-10-04 13:45:37
@xiaolou 小LouYu,大智慧!