think: 1广度优先搜索+char型map数组
sdut原题链接
汤圆の拯救计划 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 又到了汤圆星球一年一度的汤圆节了，但是大魔王却过来把汤圆公主抓走了Σ( ° △ °|||)︴ 身为汤圆骑士的QAQ蒟蒻自然而然的肩负着拯救汤圆的使命 QAQ蒟蒻经历了千辛万苦（并没有）之后，来到了大魔王的城堡，根据情报，汤圆公主就被大魔王放在城堡内，然后QAQ蒟蒻发现自己是一个路 痴，所幸的是他拿到了大魔王的城堡的地图，而且在这上面标注了自己和汤圆公主的位置，那么问题来了，聪明的你能帮他计算出需要多少单位 的时间来赶到汤圆公主的位置吗？ Ps：QAQ蒟蒻每一次都可以移动到相邻的非墙的格子中，每次移动都要花费1个单位的时间 有公共边的格子定义为相邻
Input 一开始为一个整数T代表一共有T组数据 每组测试数据的第一行有两个整数n,m (2<=n,m<=300) 接下来的n行m列为大魔王的迷宫，其中 ’#’为墙壁，‘_‘为地面 A代表QAQ蒟蒻，O代表汤圆公主:
Output 一组数据输出一个整数代表从QAQ蒟蒻到汤圆的位置的最短时间 如果QAQ蒟蒻不能到达汤圆的位置，输出-1
Example Input 2 3 3 __A _## __O 2 2 A# /#O(实际输入无’/’符号)
Example Output 6 -1
Hint
Author QAsQ
以下为accepted代码
#include <stdio.h>#include <string.h>struct node{ int x; int y; int z;}link[90000], ans;char map[300][300];int tp, op, x1, y1, visit[300][300];int fn[] = {0, 0, -1, 1};int fm[] = {1, -1, 0, 0};int BFS(int n, int m){ int tn, tm; link[tp].x = x1; link[tp].y = y1; link[tp].z = 0; tp++; visit[x1][y1] = 1; while(op < tp) { ans = link[op++]; if(map[ans.x][ans.y] == 'O') { return ans.z; } for(int i = 0; i < 4; i++) { tn = ans.x + fn[i]; tm = ans.y + fm[i]; if(tn >= 0 && tn < n && tm >= 0 && tm < m) { if(map[tn][tm] != '#' && visit[tn][tm] == 0) { link[tp].x = tn; link[tp].y = tm; link[tp].z = ans.z + 1; tp++; visit[tn][tm] = 1; } } } } return -1;}int main(){ int T, n, m, i, j; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); tp = op = 0; memset(visit, 0, sizeof(visit)); for(i = 0; i < n; i++) { scanf("%s", map[i]); } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(map[i][j] == 'A') { x1 = i, y1 = j; break; } } if(j != m) break; } printf("%d/n", BFS(n, m)); } return 0;}/***************************************************User name: Result: AcceptedTake time: 4msTake Memory: 760KBSubmit time: 2017-02-16 14:56:21****************************************************/代码是程序员的朋友，虽然没有热情，但是非常忠实。
新闻热点
疑难解答
