一道有趣的题提交(Submit) 中文

时间：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

我的WA60代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m, vis[55][55], num[50], ans = 0;
string a[55];

struct node {
	int x, y;
};

struct cmp {
	bool operator()(const node& x, const node& y) const {
		if (a[x.x][x.y] == '.' || (a[x.x][x.y] >= 'a' && a[x.x][x.y] <= 'z')) return 0;
		if (a[y.x][y.y] == '.' || (a[y.x][y.y] >= 'a' && a[y.x][y.y] <= 'z')) return 1;
		if (num[a[x.x][x.y] - 'A'] == 1) return 0;
		if (num[a[y.x][y.y] - 'A'] == 1) return 1;
//      return (a[x.x][x.y]=='.')||(num[a[x.x][x.y]-'A'])
		return 0;
	}
};

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool bfs(int x, int y) {
	int f1 = 0, f2 = 0;
	priority_queue<node, vector<node>, cmp> q;
	q.push(node{x, y});
	while (q.size()) {
		node t = q.top();
//      if(x==3&&y==5){
//          cout<<t.x<<" "<<t.y<<" "<<a[t.x][t.y]<<" "<<(a[t.x][t.y]>='a'&&a[t.x][t.y]<='z')<<"\n";
//      }
		if (a[t.x][t.y] == '*') {
			f1 = 1;
		}
		q.pop();
		vis[t.x][t.y] = 1;
		if (a[t.x][t.y] >= 'A' && a[t.x][t.y] <= 'Z' && num[a[t.x][t.y] - 'A'] == 0) continue;
		if (a[t.x][t.y] >= 'A' && a[t.x][t.y] <= 'Z') f2 = 1;
		if (a[t.x][t.y] >= 'a' && a[t.x][t.y] <= 'z') num[a[t.x][t.y] - 'a'] = 1;
		for (int i = 0; i < 4; i++) {
			int tx = t.x + dx[i];
			int ty = t.y + dy[i];
//          if(x==2&&y==5){
//              cout<<"   "<<tx<<" "<<ty<<" "<<a[tx][ty]<<"\n";
//          }
			if (tx < 1 || ty < 1 || tx > n || ty > m || a[tx][ty] == '#' || vis[tx][ty] != 0) continue;
//          if(x==2&&y==5) cout<<"can\n";
			vis[tx][ty] = 1;
			q.push(node{tx, ty});
		}
	}
//  if(x==2&&y==5){
//      cout<<"   "<<f1<<" "<<f2<<"\n";
//  }
	if (f1 == 1 && f2 == 1) return 1;
	return 0;
}
signed main(void) 
{
	ios::sync_with_stdio(0);
	cin.tie(), cout.tie();
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] = ' ' + a[i];
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '.') {
				memset(vis, 0, sizeof vis);
				memset(num, 0, sizeof num);
//              cout<<i<<" "<<j<<"\n";
				if (bfs(i, j) == 1) {
//                  cout<<i<<" "<<j<<"\n";
					ans++;
				}
			}
		}
	}
	
	cout << ans;
	
	return 0;
}