QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704811#7733. Cool, It’s Yesterday Four Times MoreSUNCHAOYIWA 1ms5844kbC++142.3kb2024-11-02 21:06:022024-11-02 21:06:10

Judging History

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

  • [2024-11-02 21:06:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5844kb
  • [2024-11-02 21:06:02]
  • 提交

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[4],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);
	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 
				int re = ex.size () - 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;
				}
				if (!re) ++ans;
			}
		}
		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;
	for (int i = 0;i < 4;++i) dd[i] = i;
	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';
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5844kb

input:

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

output:

2
1
0
0

result:

wrong answer 1st lines differ - expected: '3', found: '2'