QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#704830#7733. Cool, It’s Yesterday Four Times MoreSUNCHAOYIWA 1ms5980kbC++142.3kb2024-11-02 21:12:512024-11-02 21:12:52

Judging History

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

  • [2024-11-02 21:12:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5980kb
  • [2024-11-02 21:12:51]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
vector <pair <int,int> > p,ex;
int t,n,m,tot,ans,dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
int dd[10],out[MAX][MAX],vis[MAX][MAX],num[MAX][MAX]; 
char s[MAX][MAX];
void dfs (int x,int y);
bool check (int x,int y);
int main ()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	for (int i = 0;i < 4;++i) dd[i] = i;
	t = read ();
	while (t--)
	{
		ans = 0;ex.clear ();
		n = read ();m = read ();
		for (int i = 1;i <= n;++i) scanf ("%s",s[i] + 1);
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= m;++j) vis[i][j] = 0;
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= m;++j)
				if (s[i][j] == '.') ex.push_back ({i,j});
		for (int i = 1;i <= n;++i)
		{
			for (int j = 1;j <= m;++j)
			{
				if (s[i][j] == 'O') continue;
				for (int k = 1;k <= n;++k)
					for (int l = 1;l <= m;++l) vis[k][l] = 0;
				p.clear ();dfs (i,j);
				for (int o = 0;o < p.size ();++o) p[o] = {p[o].first - i,p[o].second - j};//delta 
				bool re = 1;
				for (auto item : ex)
				{
					if (item.first == i && item.second == j) continue;
					bool ok = 0;
					for (auto v : p)
						if (check (item.first + v.first,item.second + v.second)) {ok = 1;break;} 
					if (!ok) {re = 0;break;} 
				}
				ans += re;
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
	{
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
	{
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void dfs (int x,int y)
{
	p.push_back ({x,y});vis[x][y] = 1;
	random_shuffle (dd,dd + 4);
	for (int i = 0;i < 4;++i)
	{
		int xx = dx[dd[i]] + x,yy = dy[dd[i]] + y;
		if (1 <= xx && xx <= n && 1 <= yy && yy <= m && s[xx][yy] != 'O' && !vis[xx][yy]) dfs (xx,yy);
	}
}
bool check (int x,int y)
{
	if (!(1 <= x && x <= n && 1 <= y && y <= m)) return 1;
	return s[x][y] == 'O';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5980kb

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: 0ms
memory: 5892kb

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

result:

wrong answer 12th lines differ - expected: '7', found: '6'