一道有趣的题
时间：1s 空间：32M
题目描述：
你正在设计一个网格地图游戏，网格满足如下条件
1：恰好有一个出口
2：可能有一些门，门的标号为大写字母A-Z，每种门最多只有一个
3：可能有一些钥匙，钥匙的标号为小写字母a-z，每种钥匙只能打开对应的大写字母的门
4：可能有一些空地，空地的标号为小数点
5：可能有一些障碍，障碍不能经过
对于一个地图，你想要知道有多少的空地可以到达出口，为了使游戏显得不那么简单，你想要知道到达出口至少开一扇门的的空地有多少个
输入格式：
第一行输入两个整数n,m， (1≤n≤50)
接下来n行每行输入m个字符 (1≤m≤50)
‘.’ 代表空地
‘#’ 代表障碍
'*'代表出口
输出格式：
输出一个整数
样例输入1：
6 7 …#.A. .#B#.#. .#.#.#. .#.#.#. .#b#.#. a#…#*
样例输出1：
10
样例输入2：
3 5 a#a#* #…#. a…A.
样例输出2：
4
提示
以下是WA20代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int vis[51][51],b[55],ans,flag=0,c,d,n,m;
char a[55][55];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){
if(x==c&&y==d&&flag==1){
ans++;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;i++){
int tx=dx[i]+x;
int ty=dy[i]+y;
if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&a[tx][ty]!='#'&&vis[tx][ty]!=1){
if(a[tx][ty]>='A'&&a[tx][ty]<='Z'){
if(b[a[tx][ty]-'0'-16]>=1){
vis[tx][ty]=1;
flag=1;
dfs(tx,ty);
}
}
else if(a[tx][ty]>='a'&&a[tx][ty]<='b'){
b[a[tx][ty]-'0'-48]+=1;
vis[tx][ty]=1;
dfs(tx,ty);
}
else{
vis[tx][ty]=1;
dfs(tx,ty);
}
}
}
vis[x][y]=0;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='*'){
c=i,d=j;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!='#'){
memset(b,0,sizeof b);
if(a[i][j]>='a'&&a[i][j]<='b'){
b[a[i][j]-'0'-48]+=1;
}
flag=0;
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
vis[x][y]=0;
}
}
dfs(i,j);
}
}
}
cout<<ans*2;
}