格子合并问题（一般并查集问题）

题目描述

判断游戏结果，并判断步数 ；

算法1

参考文献

并查集基础知识 主要考察建模能力 判断是否用并查集进行问题的解决

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 210;

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

int get(int x ,int y)
{
    return n  *  (x - 1)  + y ;
}

int main()
{
    int  m ;
    cin >> n >> m ;
    for(int i = 1 ; i <= n * n ; i ++)  p[i] = i ;
    bool flag = true ;
    int res = 0 ;
    while( m -- )
    {
        int x , y ;
        string b;
        cin >> x >> y >> b;
        if(b == "D")
        {
            int px = find(get(x , y));
            int py = find(get(x + 1 , y));
            if(px == py)
            {
                flag = false ;
                cout << ++ res << endl;
                return 0;
            }else
            {
                p[px] = py ;
                res ++ ;
            }
        }
        else{
            int px = find(get(x , y));
            int py = find(get(x , y + 1));
            if(px == py)
            {
                flag = false;
                cout << ++ res << endl;
                return 0;
            }else
            {
                p[px] = py ;
                res ++ ;
            }
        }
    }
    if(flag) cout << "draw" << endl;
    return 0 ;
}