QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#510745	#7733. Cool, It’s Yesterday Four Times More	CMing	TL	20ms	101560kb	C++17	2.5kb	2024-08-09 12:00:19	2024-08-09 12:00:20

Judging History

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

[2024-08-09 12:00:20]
评测

测评结果：TL
用时：20ms
内存：101560kb

查看

[2024-08-09 12:00:19]
提交

answer

#include<bits/stdc++.h>
using namespace std;

int n, m, mm;
const int N = 1e4;
bool f[N][N];
string g[N];
int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};


void dfs(int x, int y, int u, int v)
{
    if(g[x][y] == 'O') return;
    f[x * mm + y][u * mm + v] = true;
    for(int i = 0; i < 4; i++)
    {
        int tx = x + d[i][0], ty = y + d[i][1];
        int tu = u + d[i][0], tv = v + d[i][1];
        if(tx < 0 || tx > n || ty < 0 || ty > m) continue;
        if(tu < 0 || tu > n || tv < 0 || tv > m) continue;
        if(g[tx][ty] == 'O') continue;
        if(f[tx * mm + ty][tu * mm + tv]) continue;
        dfs(tx, ty, tu, tv);
    }    
}

void solve()
{
    memset(f, 0, sizeof f);
    cin >> n >> m;
    mm = m + 2;
    g[0] = g[n + 1] = string(m, 'O');
    for(int i = 1; i <= n; i++)
    {
        string t;
        cin >> t;
        g[i] = "O" + t + "O";        
    }
    
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= m; y++)
        {
            if(g[x][y] == 'O') continue;
            for(int u = 0; u <= n + 1; u++)
            {
                for(int v = 0; v <= m + 1; v++)
                {
                    if(x == u && y == v) continue;
                    if(g[u][v] == '.') continue;
                    dfs(x, y, u, v);
                }
            }
        }


    // for(int x = 1; x <= n; x++)
    //     for(int y = 1; y <= m; y++)
    //     {
    //         cout << x << " " << y << "\n----------------\n";
    //         for(int u = 1; u <= n; u++)
    //         {
    //             for(int v = 1; v <= m; v++)
    //                 cout << f[x * mm + y][u * mm + v] << " ";
    //             cout << "\n";
    //         }
    //         cout << "----------------\n";
    //     }


    int ans = 0;
    for(int x = 1; x <= n; x++)
        for(int y = 1; y <= m; y++)
        {
            if(g[x][y] == 'O') continue;
            bool flag = true;
            for(int u = 1; u <= n; u++)
            {
                if(!flag) break;
                for(int v = 1; v <= m; v++)
                {
                    if(x == u && y == v) continue;
                    if(!f[x * mm + y][u * mm + v])
                    {
                        flag = false;
                        break;
                    }
                }
            }

            if(flag) ans++;
        }
    
    cout << ans << "\n";
}

int main()
{
	int t = 1; 
	cin >> t;
	while(t--)
	{
		solve();
	}
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 20ms

memory: 101560kb

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

Time Limit Exceeded

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: