仙岛求药 |
您所在的位置:网站首页 › 描述李逍遥 › 仙岛求药 |
仙岛求药一共分两道,我今天把两道代码全部呈上。 第一道: 少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。 下图显示了一个迷阵的样例及李逍遥找到仙药的路线。 输入 输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始,两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义: 1) ‘@’:少年李逍遥所在的位置;2) ‘.’:可以安全通行的方格;3) ‘#’:有怪物的方格;4) ‘*’:仙药所在位置。 当在一行中读入的是两个零时,表示输入结束。 输出 对于每组测试数据,分别输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。 输入示例 8 8.@##...##....#.##.#.##....#.###.#.#...#...###.#....#.*...#...###6 5.*.#..#.....##.......#.......@9 6.#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0 输出示例 108-1 解析:一个搜索简单搞定 #include #include using namespace std; char map[22][22]; bool book[22][22]; int n,m,sx,sy,fx,fy,minn=999999,f=0; void dfs(int x,int y,int step) { int next[4][2]={{1,0}, {-1,0}, {0,1}, {0,-1}}; int nx,ny; if(x==fx && y==fy) { f=1; if(minn>=step) minn=step; return; } for(int i=0;in || nxm || ny>n>>m) { if(n==0 && m==0) break; for(int i=1;imap[i][j]; if(map[i][j]=='@') { sx=i; sy=j; } if(map[i][j]=='*') { fx=i; fy=j; } } book[sx][sy]=1; f=0; minn=999999; memset(book,0,sizeof(book)); dfs(sx,sy,0); if(f==1) cout0 && map[kx-1][ky]!='#' && book[kx-1][ky]==0) { qx.push(kx-1); qy.push(ky); book[kx-1][ky]=book[kx][ky]+1; } if(ky+10 && map[kx][ky-1]!='#' && book[kx][ky-1]==0) { qx.push(kx); qy.push(ky-1); book[kx][ky-1]=book[kx][ky]+1; } } return 10010; } int zhixian(int ax,int ay,int bx,int by) { int x=abs(ax-bx),y=abs(ay-by); return x+y; } int main() { //freopen("4.in","r",stdin); //freopen("x.txt","w",stdout); while(cin>>n>>m) { if(n==0 || m==0) break; int hh=0; for(int i=1;imap[i][j]; if(map[i][j]=='@') { lx=i; ly=j; } if(map[i][j]=='s') { sx=i; sy=j; } } int minx=999999; for(int i=1;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |