题目：http://acm.nyist.net/JudgeOnline/problem.php?pid=58
就是一道简单的BFS 练习练习搜索，一次AC
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio> using namespace std; int a[9][9] = { 1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,1,0,1,
1,0,0,1,1,0,0,0,1,
1,0,1,0,1,1,0,1,1,
1,0,0,0,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,1,0,0,1,
1,1,0,1,0,0,0,0,1,
1,1,1,1,1,1,1,1,1
};
bool bool_judge[9][9];
typedef struct point
{
int x,y,t;
point()
{
x = -1; y = -1; t = -1;
}
}point; vector<point>v;
vector<point>::iterator p;
point q; void init()
{
memset(bool_judge,false,sizeof(bool_judge));
/* for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
}
void add(point k,int t)
{
if(k.x-1 >= 0 && a[k.x - 1][k.y] == 0 && bool_judge[k.x - 1][k.y] == false)
{
q.x = k.x - 1,q.y = k.y,q.t = t;
v.push_back(q);
bool_judge[k.x - 1][k.y] = true;
} if(k.x + 1 <= 8 && a[k.x+1][k.y] == 0 && bool_judge[k.x+1][k.y] == false)
{
q.x = k.x + 1,q.y = k.y,q.t = t;
v.push_back(q);
bool_judge[k.x + 1][k.y] = true;
} if(k.y - 1 >= 0 && a[k.x][k.y - 1] == 0 && bool_judge[k.x][k.y - 1] == false)
{
q.x = k.x,q.y = k.y - 1,q.t = t;
v.push_back(q);
bool_judge[k.x][k.y - 1] = true;
} if(k.y + 1 <= 8 && a[k.x][k.y+1] == 0 && bool_judge[k.x][k.y + 1] == false)
{
q.x = k.x,q.y = k.y + 1,q.t = t;
v.push_back(q);
bool_judge[k.x][k.y + 1] = true;
}
} int BFS(int x2,int y2)
{
while(v.empty() != true)
{
q = v[0];
p = v.begin();
v.erase(p);
//printf("chu %d %d\n",q.x,q.y);
if(q.x == x2 && q.y == y2)
{
return q.t;
}
add(q,++q.t);
}
return 0;
}
int main()
{
init();
int n;
scanf("%d",&n);
int x1,y1,x2,y2;
while(n--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
q.x = x1,q.y = y1,q.t = 0;
v.push_back(q);
bool_judge[x1][y1] = true;
int sum = BFS(x2,y2);
printf("%d\n",sum);
v.clear();
init();
}
return 0;
}