NO
从起始点开始dfs，并在dfs的过程中记录门的坐标位置，并拾取钥匙。如果收集的钥匙数量足够，则从门的位置开始再次进行一次dfs，直到无法继续dfs为止。（判断收集的钥匙是否足够打开门的部分在dfs中完成，可以用queue存储可以进行dfs的起始点）
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=22; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; char s[maxn][maxn]; bool door_reach[5]; int door_xy[2][5]; int key_tot[5],key_get[5]; struct node{int x,y;}; queue<node>q; int m,n,fx,fy,tx,ty; void dfs(int x,int y) { s[x][y]='X'; for(int i=0;i<4;i++) { if(s[x+dx[i]][y+dy[i]]=='.')dfs(x+dx[i],y+dy[i]); if(s[x+dx[i]][y+dy[i]]>='a'&&s[x+dx[i]][y+dy[i]]<='e') { key_get[s[x+dx[i]][y+dy[i]]-'a']++; if(key_get[s[x+dx[i]][y+dy[i]]-'a']==key_tot[s[x+dx[i]][y+dy[i]]-'a'] &&door_reach[s[x+dx[i]][y+dy[i]]-'a']) q.push({door_xy[0][s[x+dx[i]][y+dy[i]]-'a'],door_xy[1][s[x+dx[i]][y+dy[i]]-'a']}); dfs(x+dx[i],y+dy[i]); } if(s[x+dx[i]][y+dy[i]]>='A'&&s[x+dx[i]][y+dy[i]]<='E') { door_reach[s[x+dx[i]][y+dy[i]]-'A']=true; door_xy[0][s[x+dx[i]][y+dy[i]]-'A']=x+dx[i]; door_xy[1][s[x+dx[i]][y+dy[i]]-'A']=y+dy[i]; if(key_get[s[x+dx[i]][y+dy[i]]-'A']==key_tot[s[x+dx[i]][y+dy[i]]-'A'])q.push({x+dx[i],y+dy[i]}); } } } int main() { while(scanf("%d%d",&m,&n)&&(m+n)) { memset(s,'X',sizeof s); memset(door_reach,false,sizeof door_reach); memset(key_tot,0,sizeof key_tot); memset(key_get,0,sizeof key_get); memset(door_xy,0,sizeof door_xy); while(!q.empty())q.pop(); for(int i=1;i<=m;i++)for(int j=1;j<=n;j++) { scanf(" %c",&s[i][j]); if(s[i][j]=='S')fx=i,fy=j,s[i][j]='.'; if(s[i][j]=='G')tx=i,ty=j,s[i][j]='.'; if(s[i][j]>='a'&&s[i][j]<='e')key_tot[s[i][j]-'a']++; } q.push({fx,fy}); while(!q.empty()) { node l=q.front();q.pop(); dfs(l.x,l.y); } if(s[tx][ty]=='X')printf("YES\n"); else printf("NO\n"); } return 0; } 附：感谢hqq和lyb大神帮我查错！
2:汉诺塔问题 描述 约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。 这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615 这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。 假定圆盘从小到大编号为1, 2, ... 输入 输入为一个整数后面跟三个单字符字符串。 整数为盘子的数目，后三个字符表示三个杆子的编号。 输出 输出每一步移动盘子的记录。一次移动一行。 每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。 样例输入 2 a b c 样例输出 a->1->c a->2->b c->1->b
题目说的非常清楚，直接递归解决。前半部分先将前n-1个盘子移动到第三根柱子上，然后将最大的盘子移动到第二根柱子上，最后一个部分将第三根柱子上的盘子移动到第二根柱子上。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; void hanoi(int n,char a,char b,char c) { if(n>1)hanoi(n-1,a,c,b); printf("%c->%d->%c\n",a,n,b); if(n>1)hanoi(n-1,c,b,a); } int main() { int n; char a,b,c; scanf("%d",&n); scanf(" %c %c %c",&a,&b,&c); hanoi(n,a,b,c); return 0; } 3:大盗阿福 描述 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？ 输入 输入的第一行是一个整数 T (T <= 50) ，表示一共有 T 组数据。 接下来的每组数据，第一行是一个整数 N (1 <= N <= 100, 000) ，表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。 输出 对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。 样例输入 2 3 1 8 2 4 10 7 6 14 样例输出 8 24 提示 对于第一组样例，阿福选择第 2 家店铺行窃，获得的现金数量为 8 。 对于第二组样例，阿福选择第 1 和 4 家店铺行窃，获得的现金数量为 10 + 14 = 24 。 经典的序列型动归问题。
令a[i]表示编号为i的店铺的现金数量，f[i]表示阿福从编号为1的店铺洗劫到编号为i的店铺所得的最大现金数量。
则阿福可以选择放弃这一家店铺或者洗劫这一家店铺。
因为店铺中的现金数量是正整数，所以状态转移方程为：
f[i]=max{f[i-1],f[i-2]+a[i]};
时间复杂度是O(N)，空间复杂度可以降到最低O(1)。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100010; int f[maxn]={},a[maxn]={},T,n; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i]); f[0]=a[0];f[1]=max(a[0],a[1]); for(int i=2;i<n;i++)f[i]=max(f[i-2]+a[i],f[i-1]); printf("%d\n",f[n-1]); } return 0; }
