「C言語」幅優先探索BFSの実装サンプル
C言語コード：
１．実装方法1
//単方向の検索
#include <stdio.h>
int n, side, startx,starty,endx,endy,x,y,step;
int i,j,k;
int flag[301][301],head,tail;
struct {
int x;
int y;
int step;
}queue[100000],p;
int move[8][2] = {{-1,2},{-1,-2},{1,2},{1,-2},{2,-1},{2,1},{-2,-1},{-2,1}};
void BFS() //BFS関数の定義
{
for (i=0; i<side; i++)
for (j=0; j<side; j++)
{
flag[i][j]=0;
}
head = tail = 0;
p.x = startx;
p.y = starty;
p.step = 0;
flag[startx][starty] = 1;
queue[tail++] = p;
while (head <= tail)
{
x = queue[head].x;
y = queue[head].y;
step = queue[head].step;
head++;
for (i=0; i<8; i++)
{
p.x = x + move[i][0];
p.y = y + move[i][1];
p.step = step + 1;
if (p.x<0||p.y<0||p.x>side||p.y>side||flag[p.x][p.y])
continue;
if (p.x==endx && p.y==endy)
{
printf(“%d\n", p.step);
return;
}
queue[tail++] = p;
flag[p.x][p.y] = 1;
}
}
}
int main()
{
scanf(“%d",&n);
while (n–)
{
scanf(“%d%d%d%d%d",&side, &startx, &starty, &endx, &endy);
if (startx==endx && starty==endy)
{
printf(“%d\n",0);
continue;
}
BFS();
}
return 0;
}
2.実装方法2
//全体の検索
#include <iostream>
#include <queue>
using namespace std;
int n, side, startx, starty, endx, endy;
int i, j, k, x, y;
int a[301][301], b[301][301];
int move[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
struct point
{
int x, y;
};
point l,r,lp;
queue<point> s;
queue<point> t;
void DBFS()
{
while (!s.empty())
s.pop();
while (!t.empty())
t.pop();
for (i=0; i<side; i++)
for (j=0; j<side; j++)
{
a[i][j] = b[i][j] = -1;
}
l.x = startx;
l.y = starty;
r.x = endx;
r.y = endy;
s.push(l);
t.push(r);
a[startx][starty] = 0;
b[endx][endy] = 0;
while (!(s.empty()&&t.empty()))
{
if (!s.empty())
{
l = s.front();
s.pop();
for(i=0; i<8; i++)
{
x = move[i][0] + l.x;
y = move[i][1] + l.y;
if (x<0||x>=side||y<0||y>=side)
continue;
if (a[x][y] == -1)
{
a[x][y] = a[l.x][l.y] + 1;
lp.x = x;
lp.y = y;
s.push(lp);
}
if (b[x][y] != -1)
{
cout<<a[x][y]+b[x][y]<<endl;
return;
}
}
}
if (!t.empty())
{
r = t.front();
t.pop();
for(i=0; i<8; i++)
{
x = move[i][0] + r.x;
y = move[i][1] + r.y;
if (x<0||x>=side||y<0||y>=side)
continue;
if (b[x][y] == -1)
{
b[x][y] = b[r.x][r.y] + 1;
lp.x = x;
lp.y = y;
t.push(lp);
}
if (a[x][y] != -1)
{
cout<<a[x][y]+b[x][y]<<endl;
return;
}
}
}
}
}
int main()
{
cin>>n;
while (n–)
{
cin>>side>>startx>>starty>>endx>>endy;
if (startx==endx && starty==endy)
{
cout<<0<<endl;
continue;
}
DBFS();
}
return 0;
}