QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265212#7733. Cool, It’s Yesterday Four Times Moreucup-team191#WA 1ms5696kbC++141.5kb2023-11-25 17:16:172023-11-25 17:16:18

Judging History

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

  • [2023-11-25 17:16:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5696kb
  • [2023-11-25 17:16:17]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=1010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

int t,n,m,co[N][N];
bool bio[N][N];
string h[N];
vector<pii> cu;

void dfs(int i,int j)
{
	cu.pb({i,j});
	bio[i][j]=1;
	for (int k=0;k<4;++k)
	{
		int i1=i+dx[k],j1=j+dy[k];
		if (i1<0 || j1<0 || i1>=n || j1>=m || h[i1][j1]=='O' || bio[i1][j1]) continue;
		dfs(i1,j1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>m;
		for (int i=0;i<n;++i) cin>>h[i];
		for (int i=0;i<n;++i) for (int j=0;j<m;++j) bio[i][j]=0;
		vector<vector<pii>> comps;
		for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (!bio[i][j] && h[i][j]=='.')
		{
			cu.clear();
			dfs(i,j);
			for (auto x: cu) co[x.x][x.y]=cu.size();
			comps.pb(cu);
		}
		int an=0;
		for (auto x: comps)
		{
			bool ok=1;
			for (auto y: comps) if (y!=x)
			{
				int ind=co[y[0].x][y[0].y];
				bool sub=0;
				for (auto z: y)
				{
					int offx=z.x-x[0].x,offy=z.y-x[0].y;
					bool csub=1;
					for (auto w: x)
					{
						int i1=offx+w.x,j1=offy+w.y;
						if (i1<0 || j1<0 || i1>=n || j1>=m || co[i1][j1]!=ind) csub=0;
					}
					if (csub) sub=1;
				}
				if (sub) ok=0;
			}
			if (ok) an+=x.size();
		}
		cout<<an<<en;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5696kb

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
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
7
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
3
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
0
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
3
1
3
3
4
0
2
11
2
2
4
0
4
4
3
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

wrong answer 54th lines differ - expected: '5', found: '3'