题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 205;
int p[N * N] ;
int n, m;

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n * n; i ++) p[i] = i;
    for (int i = 1; i <= m; i ++)
    {
        int x, y;
        char c;
        cin >> x >> y >> c;
        int a = (x - 1) * n + y;
        int b;
        if (c == 'D') b = x * n + y;
        else b = (x - 1) * n + y + 1;

        //cout << a << " " << b << endl;

        a = find(a), b = find(b);
        if (a == b)
        {
            cout << i;
            return 0;
        }
        p[a] = b;
    }
    cout << "draw";
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla