本文共 2032 字,大约阅读时间需要 6 分钟。
、
#include#include #include using namespace std;const int INF = 9999999;const int MAX = 102;struct Node{ int x, y; int step; int prex, prey; char c;};struct cmp{ bool operator () (const Node &a, const Node &b){ return a.step > b.step; }};Node map[MAX][MAX];int n, m;int flag;int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1}}; priority_queue ,cmp> pq;//忘记声明变量了 int sec;int bfs() { Node node; while(!pq.empty())//清空内存 pq.pop(); map[0][0].step = 0;//开始的step为0 pq.push(map[0][0]); while(!pq.empty()){ node = pq.top(); pq.pop(); if(node.x == n-1 && node.y == m-1){ flag = 1; return node.step; } for(int i = 0; i < 4; i++ ){ int nx = node.x + dir[i][0]; int ny = node.y + dir[i][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny].c =='X') continue; if(map[nx][ny].c == '.' && map[nx][ny].step > node.step+1){ map[nx][ny].step = node.step + 1; map[nx][ny].prex = node.x; map[nx][ny].prey = node.y; pq.push(map[nx][ny]); } else if(map[nx][ny].c >='1'&&map[nx][ny].c <='9' && map[nx][ny].step > node.step+map[nx][ny].c-'0'+1){ map[nx][ny].step = node.step + map[nx][ny].c-'0' + 1; map[nx][ny].prex = node.x; map[nx][ny].prey = node.y; pq.push(map[nx][ny]); } } } return -1; }void printPath(int x, int y) { if(x == 0 && y == 0) return ; printPath(map[x][y].prex,map[x][y].prey); printf("%ds:(%d,%d)->(%d,%d)\n",sec++,map[x][y].prex,map[x][y].prey,x,y); if(map[x][y].c >= '1' && map[x][y].c <= '9'){ int t = map[x][y].c-'0'; while(t--){ printf("%ds:FIGHT AT (%d,%d)\n",sec++,x,y); } } } int main() { while(scanf("%d%d",&n,&m) != EOF){ int i; // getchar(); for(i = 0; i < n; ++i ){ getchar();//每行末尾都有 换行符 for(int j = 0; j < m; ++j){ map[i][j].c = getchar(); map[i][j].x = i; map[i][j].y = j; map[i][j].step = INF;//step无穷大 代替了 vis } }// for(int i = 0; i < n; i++ ){// for(int j = 0; j < m; ++j){// cout <
转载地址:http://rlimi.baihongyu.com/