成华区微信网站建设公,广州 四合一网站开发,外包岗位可以去吗,app商城软件迷宫寻宝#xff08;一#xff09;
时间限制#xff1a; 1000 ms | 内存限制#xff1a; 65535 KB
难度#xff1a; 4 描述一个叫ACM的寻宝者找到了一个藏宝图#xff0c;它根据藏宝图找到了一个迷宫#xff0c;这是一个很特别的迷宫#xff0c;迷宫里有N个编过…迷宫寻宝一
时间限制 1000 ms | 内存限制 65535 KB
难度 4
描述 一个叫ACM的寻宝者找到了一个藏宝图它根据藏宝图找到了一个迷宫这是一个很特别的迷宫迷宫里有N个编过号的门N5)它们分别被编号为A,B,C,D,E.为了找到宝藏ACM必须打开门但是开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙每个门都至少有一把钥匙例如现在A门有三把钥匙ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM他能不能顺利的得到宝藏。 输入 输入可能会有多组测试数据不超过10组。 每组测试数据的第一行包含了两个整数M,N(1N,M20)分别代表了迷宫的行和列。接下来的M每行有N个字符描述了迷宫的布局。其中每个字符的含义如下 .表示可以走的路 S:表示ACM的出发点 G表示宝藏的位置 X表示这里有墙ACM无法进入或者穿过。 A,B,C,D,E表示这里是门a,b,c,d,e表示对应大写字母的门上的钥匙。 注意ACM只能在迷宫里向上下左右四个方向移动。 最后输入0 0表示输入结束。 输出每行输出一个YES表示ACM能找到宝藏输出NO表示ACM找不到宝藏。样例输入 4 4 S.X.a.X. ..XG .... 3 4S.Xa.aXB b.AG 0 0 样例输出 YES NO 题意就是 给你个图大写字母表示门 小写字母表示对应的钥匙 必须要把对应门所有钥匙集齐后 才能开门S是起点 G是终点 问能否抵达终点注意这道题难点其实就是搜索 那么搜索到门的时候如何处理呢 我如何知道在搜索到门之前是否能够搜全足够的钥匙呢那么我们不如循环广搜 只要本次BFS搜到钥匙就继续广搜 前面的BFS先搜到钥匙 后面的去匹配把能搜的钥匙搜齐全了 在去破门 如果门中有钥匙 就再搜索 直到有结果 #includecstdio
#includecstring
#includequeue
#includealgorithm
#includeiostream
using namespace std;
char p[21][21];
struct node
{int x,y;
};
int b[5],has[5];// 0 a 1 b 2 c 3 d 4 e b表示图中钥匙有多少个 has表示最后阶段性搜索能搜到多少个
int dir[][2]{{-1,0},{0,1},{1,0},{0,-1}};
int main()
{int n,m;node s,e;while(cinnm,n||m){memset(b,0,sizeof(b));memset(has,0,sizeof(has));for(int i1;in;i){for(int j1;jm;j){char c;cinc;p[i][j]c;if(cS)s.xi,s.yj;else if(islower(c))b[c-a];//记录一共有多少个钥匙}}bool bok[21][21];queuenodeq;q.push(s);bok[s.x][s.y]1;bool f0,ss1;//f 表示有没有结果 ss表示这一次搜索有没有新的钥匙while(ss!f){ss0;while(!q.empty())q.pop();memset(bok,0,sizeof(bok)); q.push(s);bok[s.x][s.y]1;while(!q.empty()){node a,bb;a q.front();q.pop();char c p[a.x][a.y];if(cG){f 1;puts(YES);break;}else if(c!Sisupper(c)has[c32-a] ! b[c32-a]){continue;//如果这个门的钥匙没集齐 就不能向下执行}for(int i0;i4;i){int tx,ty;tx a.xdir[i][0];ty a.ydir[i][1];if(txntymtxty!bok[tx][ty]p[tx][ty]!X){if(islower(p[tx][ty])){//该点是钥匙 就记录下来 该点置位为.has[p[tx][ty]-a];p[tx][ty].;ss1;} bb.xtx,bb.yty;q.push(bb);bok[tx][ty]1; }}}}if(!f)puts(NO); }return 0;
}
