QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328077#833. Cells BlockingTerdyWA 0ms3712kbC++141.4kb2024-02-15 16:54:562024-02-15 16:55:01

Judging History

你现在查看的是最新测评结果

  • [2024-02-15 16:55:01]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-02-15 16:54:56]
  • 提交

answer

# include <bits/stdc++.h>

using namespace std;

# define int long long
# define PII pair< int , int >
# define MP make_pair
# define fi first
# define se second

const int N = 3e3 + 5;
int n , m , cnt , ans , f[N][N] , g[N][N];
char mp[N][N];
vector< int > vec[N<<1];

signed main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> mp[i][j] , cnt += mp[i][j] == '.';
	f[1][1] = mp[1][1] == '.';
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(mp[i][j] == '.') f[i][j] = f[i][j - 1] | f[i - 1][j];
	g[n][m] = mp[n][m] == '.';
	for(int i = n; i; i--) for(int j = m; j; j--) if(mp[i][j] == '.') g[i][j] = g[i][j + 1] | g[i + 1][j];
	if(!f[n][m]) return cout << cnt * (cnt - 1) / 2 , 0;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(f[i][j] && g[i][j]) vec[i + j].push_back(i);
	for(int i = 2; i <= n + m; i++) if(vec[i].size() == 1) ans += --cnt;
	for(int i = 2; i <= n + m; i++)
	{
		auto &v = vec[i];
		if(v.size() == 1) continue ;
		int l = v[1] , r = v[v.size() - 1];
		if(l == r) ans++;
		for(int j = i + 1; j <= n + m; j++)
		{
			if(mp[l][j - l] == '*') l++;
			if(mp[r + 1][j - (r + 1)] == '.') r++;
			if(l == r && vec[j].size() > 1) ans++;
		}
		l = v[0] , r = v[v.size() - 2];
		for(int j = i + 1; j <= n + m; j++)
		{
			if(mp[l][j - l] == '*') l++;
			if(mp[r + 1][j - (r + 1)] == '.') r++;
			if(l == r && vec[j].size() > 1) ans++;
		}
	}
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3712kb

input:

3 3
...
...
...

output:

36

result:

wrong answer 1st numbers differ - expected: '17', found: '36'