C - Nuske vs Phantom Thnook
题意：
n*m的网格，每个格子可能是蓝色， 可能是白色，问一个子矩阵内，蓝色方格的联通块数。
输入的数据中，保证蓝色点之间只有一条路径（或者没有）。
分析：
因为任意蓝点之间只有一条路径，如果在相邻的蓝点之间连一条边后，也就是整张图没有环，在一个森林内，求一个些点构成的树的数量。
结论：联通块数=总节点数-边数。
因为，没加入一条边，会减少一个联通块，（即减少一棵树），加入了n条，就减去了n个。
代码：
1 #include2 #include 3 #include 4 using namespace std; 5 6 inline int read() { 7 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 8 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; 9 }10 11 const int N = 2005;12 char s[N][N];13 int s1[N][N], s2[N][N], s3[N][N];14 15 int main() {16 int n = read(), m = read(), Q = read();17 for (int i=1; i<=n; ++i) scanf("%s",s[i] + 1);18 for (int i=1; i<=n; ++i) {19 for (int j=1; j<=m; ++j) {20 s1[i][j] = s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1];21 s2[i][j] = s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1];22 s3[i][j] = s3[i - 1][j] + s3[i][j - 1] - s3[i - 1][j - 1];23 if (s[i][j] == '1') {24 s1[i][j] ++;25 if (s[i][j] == s[i - 1][j]) s2[i][j] ++;26 if (s[i][j] == s[i][j - 1]) s3[i][j] ++;27 }28 }29 }30 while (Q--) {31 int a1 = read(), b1 = read(), a2 = read(), b2 = read();32 int t1 = s1[a2][b2] - s1[a2][b1 - 1] - s1[a1 - 1][b2] + s1[a1 - 1][b1 - 1];33 int t2 = s2[a2][b2] - s2[a2][b1 - 1] - s2[a1][b2] + s2[a1][b1 - 1];34 int t3 = s3[a2][b2] - s3[a2][b1] - s3[a1 - 1][b2] + s3[a1 - 1][b1];35 printf("%d\n",t1 - t2 - t3);36 }37 return 0;38 }