QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#470895	#6398. Puzzle: Tapa	UESTC_Snow_Halation^#	RE	0ms	3716kb	C++14	3.6kb	2024-07-10 16:50:48	2024-07-10 16:50:48

Judging History

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

[2024-07-10 16:50:48]
评测

测评结果：RE
用时：0ms
内存：3716kb

查看

[2024-07-10 16:50:48]
提交

answer

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 107;

int n, m;
string S[N];
int mp[N][N], cnt;
int timeq, dfn[N * N], match[N * N];
vector<int> g[N];
int tag[N * N];

bool dfs(int u)
{
    for (int v : g[u])
    {
        if (dfn[v] == timeq)
            continue;
        dfn[v] = timeq;
        if (!match[v] || dfs(match[v]))
        {
            match[v] = u;
            return true;
        }
    }
    return false;
}

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

bool check(int i, int j)
{
    return ((i / 2) & 1) ^ ((j / 2) & 1);
}

int main()
{
    // ios::sync_with_stdio(false);
    cin >> n >> m;
    n--, m--;
    for (int i = 0; i <= 2 * n; i++)
        cin >> S[i];
    for (int i = 0; i <= 2 * n; i += 2)
        for (int j = 0; j <= 2 * m; j += 2)
        {
            mp[i][j] = ++cnt;
            if ((!i || i == 2 * n) && (!j || j == 2 * m) && S[i][j] == '2')
                tag[cnt] = 1;
            else if ((!i || !j || i == 2 * n || j == 2 * m) && S[i][j] == '4')
                tag[cnt] = 2;
            else if (S[i][j] == '7')
                tag[cnt] = 3;
        }
    // for (int i = 1; i <= cnt; i++)
    //     cout << tag[i] << " ";
    // cout << endl;
    // return 0;
    int w = 0;
    for (int i = 0; i <= 2 * n; i += 2)
        for (int j = 0; j <= 2 * m; j += 2)
            w += (check(i, j) > 0 ? 1 : -1) * (tag[mp[i][j]] > 0);
    if (w)
    {
        cout << "NO";
        return 0;
    }
    for (int i = 0; i <= 2 * n; i += 2)
        for (int j = 0; j <= 2 * m; j += 2)
        {
            if (check(i, j) || !tag[mp[i][j]])
                continue;
            for (int k = 0; k < 4; k++)
            {
                int xx = i + 2 * dx[k],
                    yy = j + 2 * dy[k];
                if (xx < 0 || xx > 2 * n || yy < 0 || yy > 2 * m || !tag[mp[xx][yy]])
                    continue;
                if (!(k & 1) && tag[mp[i][j]] == 2 && m == 1)
                    continue;
                if ((k & 1) && tag[mp[i][j]] == 2 && n == 1)
                    continue;
                if ((tag[mp[i][j]] == 3) ^ (tag[mp[xx][yy]] != 3))
                    g[mp[i][j]].push_back(mp[xx][yy]);
            }
        }
    for (int i = 0; i <= 2 * n; i += 2)
        for (int j = 0; j <= 2 * m; j += 2)
        {
            if (check(i, j) || !tag[mp[i][j]])
                continue;
            timeq++;
            if (!dfs(mp[i][j]))
            {
                cout << "NO";
                return 0;
            }
        }
    cout << "YES\n";
    for (int i = 0; i <= 2 * n; i += 2)
        for (int j = 0; j <= 2 * m; j += 2)
            if (check(i, j) && tag[mp[i][j]])
            {
                const int &ret = mp[i][j];
                if (ret - 1 == match[ret])
                    S[i][j - 1] = '!';
                else if (ret + 1 == match[ret])
                    S[i][j + 1] = '!';
                else if (ret + m + 1 == match[ret])
                    S[i + 1][j] = '!';
                else
                    S[i - 1][j] = '!';
            }
    for (int i = 0; i <= 2 * n; i++)
        for (int j = 0; j <= 2 * m; j++)
            if (S[i][j] == '!')
                S[i][j] = '.';
            else if (S[i][j] == '.')
                S[i][j] = '#';
    // cout << "!!!" ;
    for (int i = 0; i <= 2 * n; i++)
        cout << S[i] << endl;
}

/*
3 2
2.2
...
4.4
...
2.2
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3588kb

input:

3 3
2.4.3
.....
5.8.5
.....
3.5.3

output:

YES
2.4#3
#####
5#8#5
#####
3#5#3

result:

ok Correct.

Test #2:

score: 0

Accepted

time: 0ms

memory: 3652kb

input:

3 3
3.4.3
.....
5.7.5
.....
3.5.3

output:

NO

result:

ok Correct.

Test #3:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

2 2
2.2
...
2.2

output:

YES
2.2
###
2.2

result:

ok Correct.

Test #4:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

2 50
2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3
...................................................................................................
2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #5:

score: 0

Accepted

time: 0ms

memory: 3716kb

input:

2 50
2.4.4.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.4.4.5.5.5.4.5.4.4.4.5.4.4.5.4.4.5.5.5.5.4.4.5.5.5.5.5.2
...................................................................................................
3.5.4.5.5.5.5.5.5.5.5.5.5.5.4.5.5.5.5.4.5.5.5.5.4.4.5.4.5.4.5.5.5.5.5.4.4.5.5.5.4.4.5.5.5.5.5.4...

output:

NO

result:

ok Correct.

Test #6:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

50 2
3.2
...
5.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.4
...
5.4
...
4.4
...
5.5
...
5.5
...
4.4
...
5.4
...
5.4
...
5.5
...
4.5
...
4.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
...
5.5
......

output:

NO

result:

ok Correct.

Test #7:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

50 2
3.3
...
5.4
...
5.4
...
5.4
...
5.4
...
5.5
...
4.4
...
4.4
...
5.5
...
4.4
...
5.5
...
5.5
...
5.5
...
5.5
...
4.5
...
5.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.4
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.5
...
4.5
...
4.5
...
4.5
...
5.5
...
5.4
...
5.4
...
5.5
...
5.5
...
4.4
...
4.4
......

output:

NO

result:

ok Correct.

Test #8:

score: -100

Runtime Error

input:

3 50
3.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.5.5.4.4.5.5.5.5.5.5.5.5.4.4.5.5.4.4.5.4.4.5.3
...................................................................................................
4.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.7.7.7.7.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.8.7.7.8...