QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546859#7733. Cool, It’s Yesterday Four Times Morepzc2004#WA 1ms3944kbC++142.6kb2024-09-04 14:50:342024-09-04 14:50:35

Judging History

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

  • [2024-09-04 14:50:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3944kb
  • [2024-09-04 14:50:34]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
template<class T>inline void read(T &x){
	x=0;
	char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))x=x*10+(c&15),c=getchar();
}
int n, m;
// int f[5005];
// unsigned int b[1005][1005];
// unsigned int tt=4294967295u;
char a[1005][1005];
bitset<1005> A[1005], B[1005];
bool vis[1005][1005];

const int dx[]= {-1, 0, 1, 0}, dy[]= {0, -1, 0, 1};
int mnx, mxx, mny, mxy;
int dfs(int sx, int sy) {
	static int top, sta[1005][2];
	top=1, sta[top][0]=sx, sta[top][1]=sy;
	int res=0;
	while(top) {
		int x=sta[top][0], y=sta[top][1];
		if(x-sx<mnx) mnx=x-sx;
		else if(x-sx>mxx) mxx=x-sx;
		if(y-sy<mny) mny=y-sy;
		else if(y-sy>mxy) mxy=y-sy;
		vis[x][y]=1;
		// fprintf(stderr, "%d %d\n", x, y);
		--top;
		rep(d, 0, 3) {
			int nx=x+dx[d], ny=y+dy[d];
			if(nx>=0 && nx<n && ny>=0 && ny<m) {
				if(a[nx][ny]=='.' && !vis[nx][ny]) {
					sta[++top][0]=nx, sta[top][1]=ny;
				}
			}
		}
		++res;
	}
	return res;
}

int main(){
	int T_T;
	scanf("%d", &T_T);
	while(T_T--) {
		rep(i, 0, n-1) rep(j, 0, m-1) {
			vis[i][j]=0;
		}
		// puts("??");
		scanf("%d%d", &n, &m);
		rep(i, 0, n-1) {
			scanf("\n%s", a[i]);
			rep(j, 0, m-1) {
				A[i][j]=(a[i][j]=='.');
			}
		}
		int ans=0;
		rep(i, 0, n-1) rep(j, 0, m-1) {
			// fprintf(stderr, "%d %d\n", i, j);
			if(a[i][j]=='.' && !vis[i][j]) {
				mnx=0, mxx=0;
				mny=0, mxy=0;
				int cnt=dfs(i, j);
				rep(u, mnx, mxx) {
					B[u-mnx].reset();
					rep(v, mny, mxy) {
						B[u-mnx][v-mny]=A[i+u][j+v];
					}
				}
				int lenx=mxx-mnx+1, leny=mxy-mny+1;
				// printf("i = %d, j = %d, lenx = %d, leny = %d\n", i, j, lenx, leny);
				// printf("B: %d %d, A: %d\n", (int) B[0][0], (int) B[0][1], (int) A[0][0]);
				bool suc=1;
				rep(x, 0, n-lenx) rep(y, 0, m-leny) if(x!=i+mnx || y!=j+mny) {
					bool res=1;
					// puts("????F?ASDF?SA?DF");
					rep(u, 0, lenx-1) if((A[x+u]>>y&B[u])!=B[u]) {
						res=0;
						break;
					}
					if(res) {
						// printf("%d %d %d %d x\n", i, j, x, y);
						suc=0;
						break;
					}
				}
				if(suc) {
					ans+=cnt;
				}
			}
		}
		printf("%d\n", ans);
		
//		for(int i = 1; i <= n; i++) {
//			for(int j = 1, k = 0; j <= m; j++) {
//				if(j&31==1) k++, b[k]=0;
//				b[k]=b[k]*2+(a[i][j]=='.');
//			}
//		}
//		for(int i = 1; i <= n; i++)
//			for(int j = 1; j <= m; j++) if(a[i][j]=='.') {
//				int t=0;
//				if(a[i-1][j]=='.') t=1;
//				if(a[i][j-1]=='.') t=1;
//				if(!t) num++;
//			}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3940kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3944kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
7
11
4
4
0
6
5
2
0
1
6
4
6
2
0
0
6
3
3
1
4
1
0
7
5
2
3
7
3
0
8
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
9
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
8
7
1
6
2
2
3
4
5
2
1
0
1
12
3
4
14
0
3
2
1
0
0
4
3
1
4
3
10
3
0
3
6
2
5
1
3
3
4
0
2
13
2
2
4
0
4
4
6
2
1
2
3
0
5
0
20
4
3
2
6
0
8
3
...

result:

wrong answer 13th lines differ - expected: '9', found: '11'