题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4020
很简单的一个bfs题，是我想多了。
顺便学习一下C++的STL中的vector的用法：https://www.cnblogs.com/youpeng/p/10779019.html
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 300005;
vector<int> vec[maxn];
vector<bool> vis[maxn];
//前两个是横着走，后两个是竖着走
int gox[4] = {0, 0, -1, 1};
int goy[4] = {-1, 1, 0, 0};
int test;
int n, m;
int sx, sy, ex, ey;
struct node {
int x, y;
int dis;
};
bool judge(node nex) {
if (nex.x < 1 || nex.x > n || nex.y < 1 || nex.y > m || vis[nex.x][nex.y])
return false;
else
return true;
}
int bfs() {
node cu, ne;
cu.x = sx, cu.y = sy;
cu.dis = 0;
vis[cu.x][cu.y] = true;
queue<node> q;
q.push(cu);
while (!q.empty()) {
cu = q.front();
q.pop();
//判断是否满足条件
if (cu.x == ex && cu.y == ey) {
return cu.dis;
}
int status = vec[cu.x][cu.y];
if (cu.dis % 2) {
if (status)
status = 0;
else
status = 1;
}
if (status) { //横着走
for (int i = 0; i < 2; i++) {
ne.x = cu.x + gox[i];
ne.y = cu.y + goy[i];
if (judge(ne)) {
vis[ne.x][ne.y] = true;
ne.dis = cu.dis + 1;
q.push(ne);
}
}
} else { //竖着走
for (int i = 2; i < 4; i++) {
ne.x = cu.x + gox[i];
ne.y = cu.y + goy[i];
if (judge(ne)) {
vis[ne.x][ne.y] = true;
ne.dis = cu.dis + 1;
q.push(ne);
}
}
}
}
return -1;
}
int main() {
scanf("%d", &test);
while (test--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) {
vec[i].clear();
vis[i].clear();
}
int x;
for (int i = 1; i <= n; i++) {
vec[i].push_back(0);
vis[i].push_back(false);
for (int j = 1; j <= m; j++) {
scanf("%d", &x);
vec[i].push_back(x);
vis[i].push_back(false);
}
}
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
int ans = bfs();
if (ans >= 0) {
printf("%d\n", ans);
} else {
printf("-1\n");
}
}
return 0;
}