题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40010;
int n,m;
int p[N];
int get(int x,int y){
return x * n + y;
}
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n * n; i ++ ){
p[i] = i;
}
int res = 0;
for(int i = 1; i <= m; i ++ ){
int x,y;
char d;
cin >> x >> y >> d;
x -- ,y --;
int a = get(x,y);
int b;
if(d == 'D'){
b = get(x + 1,y);
}else{
b = get(x ,y+ 1);
}
int pa = find(a),pb = find(b);
if(pa == pb){
res = i;
break;
}
p[pa] = pb;
}
if(!res){
cout << "draw";
}else{
cout << res;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla