算法分析

并查集(典型并查集判断是否存在环的问题)

• 1、将每个坐标看成一个点值，为了方便计算，将所有的坐标横纵坐标都减1，第一个位置即(1,1)看成是0，(1,2)看成是1，依次类推，将所有的坐标横纵坐标都减1后，假设当前点是(x,y),则该点的映射值是a = (x * n + y)，
  若向下画，则b = [(x + 1) * n + y],若向右画，则b = [x * n + y - 1]

• 2、枚举所有操作，通过并查集操作判断a和b是否在同一个集合，

  • 若在同一个集合则标记此操作可以让格子形成环
  • 若不在同一个集合，则需要将两个集合进行合并

时间复杂度

并查集操作接近$O(1)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

    static int N = 201 * 201 + 10;
    static int n,m;
    static int[] p = new int[N];
    static int get(int x,int y)
    {
        return x * n + y;
    }
    static int find(int x)
    {
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for(int i = 0;i < n * n;i ++) p[i] = i;
        int res = 0;
        for(int i = 1;i <= m;i ++)
        {
            String[] s2= br.readLine().split(" ");
            int x = Integer.parseInt(s2[0]) - 1;
            int y = Integer.parseInt(s2[1]) - 1;
            String d = s2[2];
            int a = get(x,y);
            int b ;
            if(d.equals("D")) b = get(x + 1,y);
            else b = get(x,y + 1);

            int pa = find(a);
            int pb = find(b);
            if(pa == pb)
            {
                res = i;
                break;
            }
            p[pa] = pb;
        }
        if(res == 0) System.out.println("draw");
        else System.out.println(res);
    }
}