@@ -0,0 +1,1841 @@
+class MaxMatch %7B%0A    List%3CInteger%3E%5B%5D edges;%0A    int n, m;%0A    int%5B%5D visited, prev;%0A    public MaxMatch(int n, int m) %7B%0A        this.n = n;%0A        this.edges = new List%5Bn%5D; %0A        for(int i = 0; i %3C n; ++i) %7B%0A            this.edges%5Bi%5D = new ArrayList%3CInteger%3E();%0A        %7D%0A        %0A        this.m = m;%0A        this.prev = new int%5Bm%5D;%0A        for(int i = 0; i %3C m; ++i) %7B%0A            prev%5Bi%5D = -1; %0A        %7D%0A    %7D%0A    public void addEdge(int v, int u) %7B%0A        edges%5Bv%5D.add(u);%0A    %7D%0A    private int dfs(int x) %7B%0A        for(int y : edges%5Bx%5D) %7B%0A            if(visited%5By%5D == 1) continue;%0A            visited%5By%5D = 1;%0A            if(prev%5By%5D == -1 %7C%7C dfs(prev%5By%5D) == 1) %7B%0A                prev%5By%5D = x;%0A                return 1;%0A            %7D%0A        %7D%0A        return 0;%0A    %7D%0A    public int solve() %7B%0A        int ret = 0;%0A        for(int i = 0; i %3C n; ++i) %7B%0A            this.visited = new int%5Bm%5D;%0A            ret += dfs(i);%0A        %7D%0A        return ret;%0A    %7D%0A%7D%0A%0Aclass Solution %7B%0A    public int maxStudents(char%5B%5D%5B%5D seats) %7B%0A        int n = seats.length;%0A        int m = seats%5B0%5D.length;%0A        MaxMatch mm = new MaxMatch(n * m, n * m);%0A        int%5B%5D dx = %7B0, 0, 1, -1, 1, -1%7D;%0A        int%5B%5D dy = %7B1, -1, 1, -1, -1, 1%7D;%0A        int total = 0;%0A        for(int i = 0; i %3C n; ++i) %7B%0A            for(int j = 0; j %3C m; ++j) %7B%0A                if(seats%5Bi%5D%5Bj%5D == '#') continue;%0A                total += 1;%0A                if(j %25 2 != 0) continue;%0A                for(int k = 0; k %3C 6; ++k) %7B%0A                    int x = i + dx%5Bk%5D;%0A                    int y = j + dy%5Bk%5D;%0A                    if(x %3C 0 %7C%7C y %3C 0 %7C%7C x %3E= n %7C%7C y %3E= m) continue;%0A                    if(seats%5Bx%5D%5By%5D == '.') %7B%0A                        mm.addEdge(i * m + j, x * m + y);%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return total - mm.solve();%0A    %7D%0A%7D%0A

Create lc1349.java