Submission #69076995

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 505;
int n, q, A[N][N], sum[N][N], U, D, L, R;

int main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    vector<string> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    for(int i = 0; i < n - 1; i++) 
        for(int j = 0; j < n - 1; j++) 
            if(a[i][j] == '.' && a[i][j + 1] == '.' && a[i + 1][j] == '.' && a[i + 1][j + 1] == '.') 
                A[i][j] = 1;
                
    for(int i = 0; i < n - 1; i++) 
        for(int j = 0; j < n - 1; j++) 
            sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + A[i][j];
    
    while(q--) {
        cin >> U >> D >> L >> R;
        int r1 = U - 1, r2 = D - 2, c1 = L - 1, c2 = R - 2;
        if(r1 > r2 || c1 > c2) cout << "0\n";
        else cout << sum[r2 + 1][c2 + 1] - sum[r1][c2 + 1] - sum[r2 + 1][c1] + sum[r1][c1] << '\n';
    }
    
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result