题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4020
题意
给出一张地图 以及起点和终点 求是否能从起点走到终点 如果能 求出最小步数 如果不能 输出 -1 然后地图上的0表示在这个点 只能 上下走，，1 只能 左右走
没走一步 地图上 每个1 都变成 0 每个0 都变成 1
思路 那么地图变化 可以用 步数 % 2 来求得 如果 步数 % 2 是 1 那么此时 1 就是 0 0 就是 1 如果 步数 % 2 是 0 那么就按照原地图来算 因为 n 或者 m 特别大 所以用 vector 来保存 地图 用一个 pair(int, int) 前者保存地图 后者保存标记
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1); const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 5; const int MOD = 1e9 + 7; int Move[2][2][2] { -1, 0, 1, 0, 0,-1, 0, 1, }; vector < vector <pii> > G; vector <pii> tmp; int sx, sy, ex, ey; int ans; int n, m; struct Node { int x, y, step; }temp; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) return false; return true; } queue <Node> q; void bfs() { while (!q.empty()) { int x = q.front().x; int y = q.front().y; int step = q.front().step; q.pop(); if (x == ex && y == ey) { ans = step; return; } int d; if (step % 2) d = !G[x][y].first; else d = G[x][y].first; for (int i = 0; i < 2; i++) { temp.x = x + Move[d][i][0]; temp.y = y + Move[d][i][1]; if (ok(temp.x, temp.y) && G[temp.x][temp.y].second == 0) { temp.step = step + 1; q.push(temp); G[temp.x][temp.y].second = 1; } } } } int main() { int t; cin >> t; while (t--) { G.clear(); int num; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { tmp.clear(); for (int j = 0; j < m; j++) { scanf("%d", &num); tmp.pb(pii(num, 0)); } G.pb(tmp); } scanf("%d%d%d%d", &sx, &sy, &ex, &ey); sx--, sy--, ex--, ey--; while (!q.empty()) q.pop(); temp.x = sx; temp.y = sy; temp.step = 0; q.push(temp); ans = -1; bfs(); cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433133.html
相关资源：JAVA上百实例源码以及开源项目