算法设计与复杂性理论 第一次上机 仙岛求药

总时间限制:  1000ms  内存限制:  65536kB 描述 少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 下图 显示了一个迷阵的样例及李逍遥找到仙药的路线. 输入 输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:  1) ‘@’：少年李逍遥所在的位置； 2) ‘.’：可以安全通行的方格； 3) ‘#’：有怪物的方格； 4) ‘*’：仙药所在位置。 当在一行中读入的是两个零时，表示输入结束。 输出 对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。 样例输入 8 8 .@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#. ...#.*.. .#...### 6 5 .*.#. .#... ..##. ..... .#... ....@ 9 6 .#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0 样例输出 10 8 -1

注意这道题的输入，每行有时候会包含多余的空格信息，只能采用cin cout存储字符，用getchar或者scanf的时候会ole。

#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; int M, N; int maze[25][25]; int people; class T { public: int loc; int len; T(int a, int b) { loc = a; len = b; } }; int bfs() { queue<T> way; way.push(T(people, 0)); while(!way.empty()) { T now = way.front(); int nowLoc = now.loc; int nowLen = now.len; way.pop(); if(nowLoc - N >= 0) { switch(maze[nowLoc / N - 1][nowLoc % N]) { case (0): maze[nowLoc / N - 1][nowLoc % N] = 1; way.push(T(nowLoc - N, nowLen + 1)); break; case (2): return nowLen + 1; } } if(nowLoc % N - 1 >= 0) { switch(maze[nowLoc / N][nowLoc % N - 1]) { case (0): maze[nowLoc / N][nowLoc % N - 1] = 1; way.push(T(nowLoc - 1, nowLen + 1)); break; case (2): return nowLen + 1; } } if(nowLoc % N + 1 < N) { switch(maze[nowLoc / N][nowLoc % N + 1]) { case (0): maze[nowLoc / N][nowLoc % N + 1] = 1; way.push(T(nowLoc + 1, nowLen + 1)); break; case (2): return nowLen + 1; } } if(nowLoc / N + 1 < M) { switch(maze[nowLoc / N + 1][nowLoc % N]) { case (0): maze[nowLoc / N + 1][nowLoc % N] = 1; way.push(T(nowLoc + N, nowLen + 1)); break; case (2): return nowLen + 1; } } } return -1; } int main() { char ch; cin >> M >> N; while(M != 0 && N != 0) { for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { cin >> ch; switch(ch) { case ('@'): people = i * N + j; maze[i][j] = 1; break; case ('.'): maze[i][j] = 0; break; case ('#'): maze[i][j] = -1; break; case ('*'): maze[i][j] = 2; } } } cout << bfs() << endl; cin >> M >> N; } return 0; }

#include <iostream> #include <cstdio> #include <cstdlib> #include <string.h> #include <queue> using namespace std; int m, n; int maze[25][25]; int x, y; typedef struct position { int row; int col; int pace; }pos; int bfs() { queue<pos> q; int p = -1; pos start; start.row = x; start.col = y; start.pace = 0; q.push(start); while(!q.empty()) { pos now = q.front(); q.pop(); int x1 = now.row; int y1 = now.col; if(x1 > 1) { switch(maze[x1 - 1][y1]) { case 0: pos next; next.row = x1 - 1; next.col = y1; next.pace = now.pace + 1; q.push(next); maze[x1 - 1][y1] = 1; break; case 2: return now.pace + 1; } } if(x1 < m) { switch(maze[x1 + 1][y1]) { case 0: pos next; next.row = x1 + 1; next.col = y1; next.pace = now.pace + 1; q.push(next); maze[x1 + 1][y1] = 1; break; case 2: return now.pace + 1; } } if(y1 > 1) { switch(maze[x1][y1 - 1]) { case 0: pos next; next.row = x1; next.col = y1 - 1; next.pace = now.pace + 1; q.push(next); maze[x1][y1 - 1] = 1; break; case 2: return now.pace + 1; } } if(y1 < n) { switch(maze[x1][y1 + 1]) { case 0: pos next; next.row = x1; next.col = y1 + 1; next.pace = now.pace + 1; q.push(next); maze[x1][y1 + 1] = 1; break; case 2: return now.pace + 1; } } } return p; } int main() { //scanf("%d%d", &m, &n); cin >> m >> n; while(m != 0 || n != 0) { //getchar(); for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { char ch; //ch = getchar(); //scanf("%c", &ch); cin >> ch; switch(ch) { case '@': x = i; y = j; maze[i][j] = 1; break; case '.': maze[i][j] = 0; break; case '#': maze[i][j] = -1; break; case '*': maze[i][j] = 2; break; } } //getchar(); } //printf("%d\n", bfs()); cout << bfs() << endl; //scanf("%d%d", &m, &n); cin >> m >> n; } return 0; }