Submission #69076367

---

Source Code Expand

#include<iostream>
using namespace std;
#define int long long
const int N = 505;

int n,q,a[N][N],b[N][N],vis[N][N],res[N][N];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			char c; cin >> c;
			if(c == '.') a[i][j] = b[i][j] = 1;
		}
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=n-1;j++)
			if(b[i][j] && b[i+1][j] && b[i][j+1] && b[i+1][j+1]) vis[i][j] = 1;
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=n-1;j++)
			res[i][j] = res[i-1][j] + res[i][j-1] - res[i-1][j-1] + vis[i][j];
//	for(int i=1;i<=n-1;i++,cout<<endl)
//		for(int j=1;j<=n-1;j++)
//			cout << res[i][j] << " ";
	while(q--)
	{
		int u, d, l, r, ans = 0; cin >> u >> d >> l >> r;
		ans = res[d-1][r-1] - res[u-1][r-1] - res[d-1][l-1] + res[u-1][l-1];
		if(ans < 0) ans = 0;
		cout << ans << '\n';
	}
	return 0;
}

/*

.##...
###.#.
......

----

*/

Submission Info

Judge Result