比较忙比较累，只贴代码了。
题目：6-4 UVa439 - Knight Moves
//UVa439 - Knight Moves //Accepted 0.000s //#define _XIENAOBAN_ #include<iostream> #include<cstring> #include<queue> #define M(po) Map[po.x][po.y] using namespace std; struct poi { int x, y, weight; poi operator +(const poi &that) const { return poi{ x + that.x, y + that.y, weight}; } bool operator ==(const poi &that) const { return (x == that.x) && (y == that.y); } } op, ed; const poi dir[8] = { { 2,1 },{ -2,1 },{ 2,-1 },{ -2,-1 },{ 1,2 },{ -1,2 },{ 1,-2 },{ -1,-2 } }; bool Map[10][10]; char xstart, ystart, xend, yend; int xs, ys, xe, ye; int BFS(){ if (op == ed) return 0; queue<poi> Q; Q.push(op); M(op) = true; while (!Q.empty()) { for (int i(0);i < 8;++i){ poi nxt(Q.front() + dir[i]); if (nxt.x > 0 && nxt.y > 0 && nxt.x < 9 && nxt.y < 9 && !M(nxt)) { ++nxt.weight; if (nxt == ed) return nxt.weight; M(nxt) = true; Q.push(nxt); } } Q.pop(); } return -1; } int main() { #ifdef _XIENAOBAN_ #define gets(T) gets_s(T, 129) freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif while (scanf("%c%c %c%c", &xstart, &ystart, &xend, ¥d) == 4) { memset(Map, 0, sizeof(Map)); op.x = xstart - 96, op.y = ystart - 48, op.weight = 0; ed.x = xend - 96, ed.y = yend - 48, ed.weight = 0; printf("To get from %c%c to %c%c takes %d knight moves.\n", xstart, ystart, xend, yend, BFS()); while (getchar() != '\n'); } return 0; }题目：6-5 UVa1600 - Patrol Robot
//UVa1600 - Patrol Robot //Accepted 0.000s //#define _XIENAOBAN_ #include<iostream> #include<cstring> #include<queue> #define DONE 2333333 using namespace std; struct step { int x, y, k, mov; }; int T, m, n, k; int Map[24][24],Obst[24][24]; void judge(queue<step> &Q, step &now, int x, int y) { if (Obst[x += now.x][y += now.y] == DONE) return; int _k = (Obst[x][y] ? now.k + 1 : 0); if (_k <= k) { if (_k) { if (Map[x][y] && Map[x][y] <= _k) return; Map[x][y] = _k; } else Obst[x][y] = DONE; Q.push(step{ x, y, _k, now.mov + 1 }); } } int main() { #ifdef _XIENAOBAN_ #define gets(T) gets_s(T, 129) freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif scanf("%d", &T); while (T--) { scanf("%d%d%d", &m, &n, &k); for (int i(1);i <= m;++i) for (int j(1);j <= n;++j) scanf("%d", &Obst[i][j]); memset(Map, 0, sizeof(Map)); queue<step> Q; Q.push(step{ 1,1,0,0 }); Obst[1][1] = DONE; while (!Q.empty()) { step &now(Q.front()); if (now.x == m && now.y == n) break; if (now.x + 1 <= m) judge(Q, now, 1, 0); if (now.y + 1 <= n) judge(Q, now, 0, 1); if (now.x - 1 >= 1) judge(Q, now, -1, 0); if (now.y - 1 >= 1) judge(Q, now, 0, -1); Q.pop(); } if (Q.empty()) printf("-1\n"); else printf("%d\n", Q.front().mov); } return 0; }转载于:https://www.cnblogs.com/xienaoban/p/6798076.html
