距离我问小龙这个题怎么写,时间已经过了半年( ╯□╰ )。。
两种路径输出,递归和非递归。会写两个是因为之前忘记清空队列,结果爆栈,以为是函数递归所致,所以又写了一个非递归的。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <queue> #include <algorithm> #include <string.h> using namespace std; const int maxn = 1000; const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; typedef struct Node { int x, y, step; Node(int _x = 0, int _y = 0, int _step = 0): x(_x), y(_y), step(_step) {} bool operator <(const Node argu) const { return argu.step < step; } void out() { printf("%d %d %d\n", x, y, step); } }nn; struct Ship { int fx, fy, sx, sy; Ship(int _fx = -1, int _fy = -1, int _sx = -1, int _sy = -1): fx(_fx), fy(_fy), sx(_sx), sy(_sy) {}; }ss[maxn][maxn]; priority_queue<nn> q; int n, m; char map[maxn][maxn]; bool vis[maxn][maxn]; bool check(nn p) { if(vis[p.x][p.y]) return false; if(p.x >= n || p.x < 0 || p.y >= m || p.y < 0) return false; if(map[p.x][p.y] == 'X') return false; return true; } int out(int x, int y) { int hp = 0, fs; if(map[x][y] >= '1' && map[x][y] <= '9') hp = map[x][y] - '0'; if(ss[x][y].fx == -1 && ss[x][y].fy == -1) { if(hp) for(int i = 1; i <= hp; i++) printf("%ds:FIGHT AT (%d,%d)\n", i, x, y); return hp + 1; } fs = out(ss[x][y].fx, ss[x][y].fy); printf("%ds:(%d,%d)->(%d,%d)\n", fs, ss[x][y].fx, ss[x][y].fy, x, y); if(hp) for(int i = 1; i <= hp; i++) printf("%ds:FIGHT AT (%d,%d)\n", fs + i, x, y); return fs + hp + 1; } //void out(int x, int y) //{ // int ex = x, ey = y, tx, ty; // while(ss[ex][ey].fx != -1 && ss[ex][ey].fy != -1) // { // tx = ss[ex][ey].fx, ty = ss[ex][ey].fy; // ss[tx][ty].sx = ex, ss[tx][ty].sy = ey; // ex = tx, ey = ty; // } // int cnt = 0, hp; // while(ss[ex][ey].sx != -1 && ss[ex][ey].sy != -1) // { // hp = 0; // if(map[ex][ey] >= '1' && map[ex][ey] <= '9') // hp = map[ex][ey] - '0'; // while(hp--) // { // printf("%ds:FIGHT AT (%d,%d)\n", ++cnt, ex, ey); // } // printf("%ds:(%d,%d)->(%d,%d)\n", ++cnt, ex, ey, ss[ex][ey].sx, ss[ex][ey].sy); // tx = ss[ex][ey].sx, ty = ss[ex][ey].sy; // ex = tx, ey = ty; // } // if(map[ex][ey] >= '1' && map[ex][ey] <= '9') // { // hp = map[ex][ey] - '0'; // while(hp--) // { // printf("%ds:FIGHT AT (%d,%d)\n", ++cnt, ex, ey); // } // } //} bool bfs() { nn s; if(map[0][0] >= '1' && map[0][0] <= '9') s.step += map[0][0] - '0'; q.push(s); vis[0][0] = true; while(!q.empty()) { nn now = q.top(); q.pop(); if(now .x == n - 1 && now.y == m - 1) { printf("It takes %d seconds to reach the target position, let me show you the way.\n", now.step); out(now.x, now.y); return false; } nn next; for(int i = 0; i < 4; i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if(check(next)) { next.step = now.step + 1; if(map[next.x][next.y] >= '1' && map[next.x][next.y] <= '9') next.step += map[next.x][next.y] - '0'; q.push(next); vis[next.x][next.y] = true; ss[next.x][next.y].fx = now.x; ss[next.x][next.y].fy = now.y; } } } return true; } int main() { // freopen("1026.in", "r", stdin); while(~scanf("%d%d", &n, &m)) { while(!q.empty()) q.pop(); for(int i = 0; i < n; i++) scanf("%s", map[i]); memset(vis, false, sizeof(vis)); memset(ss, -1, sizeof(ss)); if(bfs()) printf("God please help our poor hero.\n"); printf("FINISH\n"); } return 0; }