首页 > 代码库 > HDU 1026 Ignatius and the Princess I
HDU 1026 Ignatius and the Princess I
广搜的一个简单变形,思路还是一样的,依旧是维护一个队列,将一个节点不断的扩展,扩展完后出队。
这道题还有两个特点就是:可能遇到怪兽,因此需要额外花费n秒的时间来打败它。
最终还要输出路径。
因此结构体里面prex 和 prey就是来记录下一个格子的坐标的。
因为有了怪兽所以我们不能一搜到起点就退出搜索,因为可能存在其他更快的路径,所以要全部搜完。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 const int MAX = 100000000; 9 int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 10 int row, col; 11 12 struct st 13 { 14 char cc; 15 int num, x, y, prex, prey; 16 }map[105][105]; 17 18 bool isdigit(char c) 19 { 20 return (c >= ‘0‘ && c <= ‘9‘); 21 } 22 23 void OutPut(void) 24 { 25 if(map[0][0].num != MAX) 26 { 27 int x = 0, y = 0, a, b, steps = 1; 28 printf("It takes %d seconds to reach the target position, let me show you the way.\n", map[0][0].num); 29 while(x < row - 1 || y < col - 1) 30 { 31 a = map[x][y].prex, b = map[x][y].prey; 32 if(isdigit(map[x][y].cc)) 33 for(int i = 0; i < map[x][y].cc - ‘0‘; ++i) 34 printf("%ds:FIGHT AT (%d,%d)\n", steps++, x, y); 35 printf("%ds:(%d,%d)->(%d,%d)\n", steps++, x, y, a, b); 36 x = a, y = b; 37 } 38 if(isdigit(map[x][y].cc)) 39 for(int i = 0; i < map[x][y].cc - ‘0‘; ++i) 40 printf("%ds:FIGHT AT (%d,%d)\n", steps++, x, y); 41 printf("FINISH\n"); 42 } 43 else 44 printf("God please help our poor hero.\nFINISH\n"); 45 } 46 47 void BFS(void) 48 { 49 int temp; 50 st first; 51 queue<st> qu; 52 map[row-1][col-1].num = 0; 53 if(isdigit(map[row-1][col-1].cc)) 54 map[row-1][col-1].num = map[row-1][col-1].cc - ‘0‘; 55 qu.push(map[row-1][col-1]); 56 while(!qu.empty()) 57 { 58 first = qu.front(); 59 for(int i = 0; i < 4; ++i) 60 { 61 int tx = first.x + dir[i][0]; 62 int ty = first.y + dir[i][1]; 63 if(tx<0 || tx>=row || ty<0 || ty>=col || map[tx][ty].cc == ‘X‘) 64 continue; 65 temp = first.num; 66 if(isdigit(map[tx][ty].cc)) 67 temp += map[tx][ty].cc - ‘0‘; 68 if(temp + 1 < map[tx][ty].num) 69 { 70 map[tx][ty].num = temp + 1; 71 map[tx][ty].prex = first.x; 72 map[tx][ty].prey = first.y; 73 qu.push(map[tx][ty]); 74 } 75 } 76 qu.pop(); 77 } 78 OutPut(); 79 } 80 81 int main(void) 82 { 83 #ifdef LOCAL 84 freopen("1026in.txt", "r", stdin); 85 #endif 86 87 while(scanf("%d%d", &row, &col) == 2) 88 { 89 getchar(); 90 for(int i = 0; i < row; ++i) 91 { 92 for(int j = 0; j < col; ++j) 93 { 94 scanf("%c", &map[i][j].cc); 95 map[i][j].x = i; 96 map[i][j].y = j; 97 map[i][j].num = MAX; 98 map[i][j].prex = map[i][j].prey = -1; 99 }100 getchar();101 }102 BFS();103 }104 return 0;105 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。