QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#497190	#7733. Cool, It’s Yesterday Four Times More	333zhan	WA	1ms	3484kb	C++20	3.0kb	2024-07-28 21:07:15	2024-07-28 21:07:15

Judging History

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

[2024-07-28 21:07:15]
评测

测评结果：WA
用时：1ms
内存：3484kb

查看

[2024-07-28 21:07:15]
提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

inline int read () {
    int w = 1, s = 0; char ch = getchar ();
    for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
    for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

void solve () {
	int n, m;
    cin >> n >> m;

    vector <string> s (n);
    for (int i = 0; i < n; i ++) {
        cin >> s[i];
    }

    vector a (n, vector <bool> (m));
    vector vis (n, vector <bool> (m));
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (s[i][j] == '.') {
                a[i][j] = true;
            }
        }
    }

    int ans = 0;

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (! a[i][j] || vis[i][j]) {
                continue;
            }
            vector <pair <int, int>> p;
            int maxr = j;
            int maxd = i;
            int minl = j;
            int minu = i;
            
            auto dfs = [&] (auto &&self, int x, int y) -> void {
                vis[x][y] = true;
                p.push_back ({x, y});
                maxr = max (maxr, y);
                maxd = max (maxd, x);
                minl = min (minl, y);
                minu = min (minu, x);
                for (int i = 0; i < 4; i ++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        continue;
                    }
                    if (! a[nx][ny] || vis[nx][ny]) {
                        continue;
                    }
                    self (self, nx, ny);
                }
            };
            dfs (dfs, i, j);

            int dr = maxr - minl;
            int dd = maxd - minu;
            // cerr << minu << " " << maxd << " " << minl << " " << maxr << '\n';

            bool ok = true;
            for (int x = 0; x < n - dd; x ++) {
                for (int y = 0; y < m - dr; y ++) {
                    if (x == i && y == j) {
                        continue;
                    }
                    bool flag = true;
                    for (auto [ax, ay] : p) {
                        if (! a[x + ax - minu][y + ay - minl]) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        ok = false;
                        break;
                    }
                }
                if (! ok) {
                    break;
                }
            }
            if (ok) {
                ans += p.size ();
            }
        }
    }

    cout << ans << '\n';
} 

signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);
    
	int T = 1; 
	cin >> T;
	// T = read ();

	while (T --) {
		solve ();
	}
	
	return 0;
}

/*
0 0 
2 2
3 3
4 4 

*/

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3484kb

input:

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

output:

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 3484kb

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:

result:

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