QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796193#6534. Peg SolitaireDangXAC ✓0ms3656kbC++202.9kb2024-12-01 14:02:002024-12-01 14:02:00

Judging History

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

  • [2024-12-01 14:02:00]
  • 评测
  • 测评结果：AC
  • 用时：0ms
  • 内存：3656kb
查看
  • [2024-12-01 14:02:00]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int n, m, k, ans;
int mp[20][20];
void DFS(int nowans)
{
    ans = min(nowans, ans);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 1)
            {
                if (i >= 1 && i <= n)
                {
                    // 向下走
                    if (mp[i + 1][j] == 1 && mp[i + 2][j] == 0)
                    {
                        mp[i][j] = 0;
                        mp[i + 1][j] = 0;
                        mp[i + 2][j] = 1;
                        DFS(nowans - 1);
                        mp[i][j] = 1;
                        mp[i + 1][j] = 1;
                        mp[i + 2][j] = 0;
                    }
                    // 向上走
                    if (mp[i - 1][j] == 1 && mp[i - 2][j] == 0)
                    {
                        mp[i][j] = 0;
                        mp[i - 1][j] = 0;
                        mp[i - 2][j] = 1;
                        DFS(nowans - 1);
                        mp[i][j] = 1;
                        mp[i - 1][j] = 1;
                        mp[i - 2][j] = 0;
                    }
                }
                if (j >= 1 && j <= m)
                {
                    // 向左走
                    if (mp[i][j - 1] == 1 && mp[i][j - 2] == 0)
                    {
                        mp[i][j] = 0;
                        mp[i][j - 1] = 0;
                        mp[i][j - 2] = 1;
                        DFS(nowans - 1);
                        mp[i][j] = 1;
                        mp[i][j - 1] = 1;
                        mp[i][j - 2] = 0;
                    }
                    // 向右走
                    if (mp[i][j + 1] == 1 && mp[i][j + 2] == 0)
                    {
                        mp[i][j] = 0;
                        mp[i][j + 1] = 0;
                        mp[i][j + 2] = 1;
                        DFS(nowans - 1);
                        mp[i][j] = 1;
                        mp[i][j + 1] = 1;
                        mp[i][j + 2] = 0;
                    }
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k;
        memset(mp, 0, sizeof(mp));
        for (int i = 0; i <= n + 1; i++)
        {
            mp[i][0] = -1;
            mp[i][m + 1] = -1;
        }
        for (int i = 0; i <= m + 1; i++)
        {
            mp[0][i] = -1;
            mp[n + 1][i] = -1;
        }
        for (int i = 1; i <= k; i++)
        {
            int x, y;
            cin >> x >> y;
            mp[x][y] = 1;
        }
        ans = k;
        DFS(k);
        cout << ans << endl;
    }

    return 0;
} /*Orz Orz Orz ACACAC*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3
3 4 5
2 2
1 2
1 4
3 4
1 1
1 3 3
1 1
1 2
1 3
2 1 1
2 1

output:

2
3
1

result:

ok 3 number(s): "2 3 1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

20
2 1 2
1 1
2 1
5 1 3
3 1
2 1
4 1
3 3 6
1 2
2 2
1 1
2 3
3 1
3 2
4 4 4
2 3
3 1
3 2
1 2
1 1 1
1 1
5 2 6
3 2
4 1
2 1
5 2
2 2
5 1
1 3 1
1 2
1 5 1
1 5
4 6 5
4 6
4 4
2 3
4 3
1 6
6 6 3
2 4
1 3
2 1
2 2 2
2 1
1 1
5 3 4
2 2
5 1
4 3
3 2
6 5 6
5 5
6 5
2 4
2 1
3 4
1 4
2 6 5
1 6
2 1
1 4
2 3
1 3
3 5 6
2 1
3 3
1 5...

output:

2
2
3
1
1
2
1
1
3
3
2
1
3
3
2
1
3
1
2
2

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

20
2 1 1
2 1
4 3 2
4 3
1 1
6 4 6
4 3
5 4
4 2
3 2
3 4
2 3
3 6 4
3 1
2 6
2 4
3 5
6 6 6
3 3
3 6
4 2
3 2
4 1
1 4
3 3 1
1 1
2 3 2
2 2
2 1
3 2 2
1 2
2 2
3 4 5
2 1
3 4
3 1
2 2
3 2
2 5 5
1 5
2 3
2 5
1 4
2 2
5 6 6
5 1
2 2
1 4
5 3
4 4
1 1
2 3 4
1 1
1 2
2 2
2 1
2 3 4
1 1
2 1
1 2
2 2
6 3 6
4 2
4 1
1 3
6 2
3 3
2...

output:

1
2
2
4
4
1
1
1
2
2
6
2
2
3
4
1
1
1
3
2

result:

ok 20 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

20
1 5 3
1 2
1 3
1 1
5 6 6
5 4
2 4
4 4
4 6
2 5
3 3
5 2 4
4 1
3 1
4 2
5 2
6 3 6
3 1
5 2
3 2
4 1
4 3
3 3
5 3 5
5 2
2 2
3 1
4 3
3 2
6 1 4
3 1
5 1
1 1
4 1
3 5 6
1 1
2 1
3 4
1 5
2 2
3 3
2 5 2
2 5
2 1
5 4 6
1 3
4 3
2 2
1 2
3 3
2 3
2 3 3
2 3
1 1
1 3
1 1 1
1 1
1 1 1
1 1
1 1 1
1 1
6 4 5
2 1
6 2
3 2
1 2
4 2
5...

output:

2
1
2
2
1
2
3
2
2
3
1
1
1
3
2
2
2
3
2
1

result:

ok 20 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

20
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5 2
6 6 6
2 4
3 4
3 3
4 3
4 2
5...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2

result:

ok 20 numbers
English 繁體中文 简体中文

Server Time: 2024-12-03 19:00:56 | OpenSource Project