oj.uz

답안 #663378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
663378 2022-11-26T20:32:06 Z bluebird Tracks in the Snow (BOI13_tracks) Java 11
0 / 100
 146 ms 12324 KB 
import java.io.*;
import java.util.*;
import java.lang.*;

class Solution{
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static long MOD = (long) (1e9 + 7);
    //    static long MOD = 998244353;
    static long inv2 = 499122177;
    static long MOD2 = MOD * MOD;
    static FastReader sc = new FastReader();
    static int pInf = Integer.MAX_VALUE;
    static int nInf = Integer.MIN_VALUE;
    static long ded = (long)(1e18)+9;

    public static void main(String[] args) throws Exception {
        int test = 1;
//        test = sc.nextInt();
        for (int i = 1; i <= test; i++){
//            out.print("Case #"+i+": ");
            solve();
        }
        out.flush();
        out.close();
    }
    static int n,m;
    static void solve(){
        n = sc.nextInt();
        m = sc.nextInt();
        char[][] c = new char[n][m];
        for(int i = 0; i < n; i++){
            c[i] = sc.next().toCharArray();
        }
        int[][] count = new int[n][m];
        count[0][0] = 1;
        ArrayDeque<int[]> A = new ArrayDeque<>();
        A.add(new int[]{0,0});
        boolean[][] vis = new boolean[n][m];
        vis[0][0] = true;
        int[] di = new int[]{-1,1,0,0};
        int[] dj = new int[]{0,0,1,-1};
        int ans = 0;
        while (!A.isEmpty()){
            int size = A.size();
            while (size-->0){
                int[] p = A.pollFirst();
                int ui = p[0];
                int uj = p[1];
                ans = Math.max(ans,count[ui][uj]);
                for(int k = 0; k < 4; k++){
                    int ni = ui+di[k];
                    int nj = uj+dj[k];
                    if(e(ni,nj)&&!vis[ni][nj]&&c[ni][nj]!='.'){
                        if(c[ni][nj]==c[ui][uj]){
                            A.addFirst(new int[]{ni,nj});
                            vis[ni][nj] = true;
                            count[ni][nj] = count[ui][uj];
                        }else{
                            A.addLast(new int[]{ni,nj});
                            vis[ni][nj] = true;
                            count[ni][nj] = count[ui][uj]+1;
                        }
                    }
                }
            }
        }
        out.print(ans);
    }
    static boolean e(int i, int j){
        return  i>=0&&j>=0&&i<n&&j<m;
    }

    static class BIT{
        int size;
        long[] table;
        public BIT(int size){
            this.size = size;
            table = new long[size+1];
        }
        public BIT(long[] a){
            size = a.length;
            a[0] = 0;
            table = a.clone();
            for(int i = 1; i < size; i++){
                int par = i+lsb(i);
                if(par<size) table[par] += table[i];
            }
        }
        public void update(int idx, long val){
            while (idx<=size){
                table[idx] += val;
                idx += lsb(idx);
            }
        }
        public long sum(int idx){
            long sum = 0L;
            while (idx!=0){
                sum  = add(sum,table[idx]);
                idx -= lsb(idx);
            }
            return sum;
        }
        public long preSum(int l, int r){
//            out.println(l+" "+r);
            if(l>=r)return 0;
//            return 0;
            return sum(r)-sum(l-1);
        }
        public int lsb(int i){
            return i & -i;
        }
        public long get(int i){
            return preSum(i,i-1);
        }
        public void set(int idx, int val){
            long curr = get(idx);
            update(idx,val-curr);
        }
    }
    static class Node{
        int left;
        int right;
        int max;
        public Node(int left, int right, int max){
            this.left = left;
            this.right = right;
            this.max = max;
        }
        public int size(){
            return right-left+1;
        }
    }
    static class SegTree{
        Node node;
        SegTree lChild,rChild;
        int left, right;
        public SegTree(int left, int right,int[] a){
            this.left = left;
            this.right = right;
            if(left==right){
                node = new Node(left,right,a[left]);
            }else{
                int mid = left+(right-left)/2;
                lChild = new SegTree(left,mid,a);
                rChild = new SegTree(mid+1,right,a);
                precomp();
            }
        }
        public void precomp(){
            if(left==right)return;
            node = new Node(left,right,Math.max(lChild.node.max, rChild.node.max));
        }
        public Node rangeQuery(int l ,int r,int val){
            if(right<l||left>r)return new Node(left,right,Integer.MIN_VALUE);
            else if(left>=l&&right<=r&&node.max<=val){
                return node;
            }
            Node leftNode = lChild.rangeQuery(l,r,val);
            Node rightNode = rChild.rangeQuery(l,r,val);
            if(leftNode.max<=val&&rightNode.max<=val){
                return new Node(left,right,Math.max(leftNode.max,rightNode.max));
            }
            else if(rChild.node.max<=val){
                return new Node(leftNode.left,leftNode.right,leftNode.max);
            }else {
                return new Node(rightNode.left,rightNode.right,rightNode.max);
            }
        }
        public void pointUpdate(int idx, int val){
            if (left==right){
                node.max = val;
                return;
            }
            if(idx<= lChild.right){
                lChild.pointUpdate(idx,val);
            }else{
                rChild.pointUpdate(idx,val);
            }
            precomp();
        }
    }
    static class Pair implements Comparable<Pair> {
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Pair o){
//            if(this.y==o.y){
//                return Integer.compare((int)this.x,(int)o.x);
//            }
//            return Integer.compare(this.y,o.y);

            if(this.x==o.x){
//                if(this.y==o.y){
//                    return Integer.compare((int)this.p,(int)o.p);
//                }
                return Integer.compare((int)this.y,(int)o.y);
            }
            return  Integer.compare(this.x,o.x);
        }

        @Override
        public String toString() {
            return "Pair{" + "x=" + x + ", y=" + y + '}';
//            return x+" "+y;
        }

//        public boolean equals(Pair o){
//            return this.x==o.x&&this.y==o.y;
//        }
    }
    static long lcm(long a, long b){
        return (a*b)/gcd(a,b);
    }
    public static long mul(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }
    public static long sub(long a, long b) {
        return ((a%MOD)-(b%MOD)+MOD)%MOD;
    }
    public static long add(long a, long b) {
        if((a+b)>MOD){
            return a+b-MOD;
        }else{
            return a+b;
        }
//        return ((a % MOD) + (b % MOD)) % MOD;
    }
    public static long c2(long n) {
        if ((n & 1) == 0) {
            return mul(n / 2, n - 1);
        } else {
            return mul(n, (n - 1) / 2);
        }
    }
    //Shuffle Sort
    static final Random random = new Random();
    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n); int temp= a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }
    //Brian Kernighans Algorithm
    static long countSetBits(long n) {
        if (n == 0) return 0;
        return 1 + countSetBits(n & (n - 1));
    }
    //Euclidean Algorithm
    static long gcd(long A, long B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }
    //Modular Exponentiation
    static long fastExpo(long x, long n) {
        if (n == 0) return 1;
        if ((n & 1) == 0) return fastExpo((x * x) % MOD, n / 2) % MOD;
        return ((x % MOD) * fastExpo((x * x) % MOD, (n - 1) / 2)) % MOD;
    }
    //AKS Algorithm
    static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i <= Math.sqrt(n); i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }
    public static long modinv(long x) {
        return modpow(x, MOD - 2);
    }
    public static long modpow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        long x = modpow(a, b / 2);
        x = (x * x) % MOD;
        if (b % 2 == 1) {
            return (x * a) % MOD;
        }
        return x;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 125 ms 12324 KB Execution failed because the return code was nonzero
2 Runtime error 125 ms 11952 KB Execution failed because the return code was nonzero
3 Runtime error 126 ms 12188 KB Execution failed because the return code was nonzero
4 Runtime error 129 ms 12096 KB Execution failed because the return code was nonzero
5 Runtime error 129 ms 11976 KB Execution failed because the return code was nonzero
6 Runtime error 125 ms 12068 KB Execution failed because the return code was nonzero
7 Runtime error 128 ms 12064 KB Execution failed because the return code was nonzero
8 Runtime error 133 ms 12156 KB Execution failed because the return code was nonzero
9 Runtime error 127 ms 12248 KB Execution failed because the return code was nonzero
10 Runtime error 125 ms 12160 KB Execution failed because the return code was nonzero
11 Runtime error 129 ms 12128 KB Execution failed because the return code was nonzero
12 Runtime error 128 ms 12108 KB Execution failed because the return code was nonzero
13 Runtime error 129 ms 12228 KB Execution failed because the return code was nonzero
14 Runtime error 125 ms 11964 KB Execution failed because the return code was nonzero
15 Runtime error 131 ms 12064 KB Execution failed because the return code was nonzero
16 Runtime error 131 ms 11984 KB Execution failed because the return code was nonzero
17 Runtime error 132 ms 12096 KB Execution failed because the return code was nonzero
18 Runtime error 131 ms 12236 KB Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 126 ms 12196 KB Execution failed because the return code was nonzero
2 Runtime error 134 ms 11996 KB Execution failed because the return code was nonzero
3 Runtime error 125 ms 12020 KB Execution failed because the return code was nonzero
4 Runtime error 125 ms 12040 KB Execution failed because the return code was nonzero
5 Runtime error 129 ms 12120 KB Execution failed because the return code was nonzero
6 Runtime error 129 ms 12124 KB Execution failed because the return code was nonzero
7 Runtime error 133 ms 12076 KB Execution failed because the return code was nonzero
8 Runtime error 133 ms 12160 KB Execution failed because the return code was nonzero
9 Runtime error 129 ms 12184 KB Execution failed because the return code was nonzero
10 Runtime error 130 ms 12128 KB Execution failed because the return code was nonzero
11 Runtime error 133 ms 12188 KB Execution failed because the return code was nonzero
12 Runtime error 133 ms 12008 KB Execution failed because the return code was nonzero
13 Runtime error 128 ms 12100 KB Execution failed because the return code was nonzero
14 Runtime error 128 ms 12080 KB Execution failed because the return code was nonzero
15 Runtime error 126 ms 12088 KB Execution failed because the return code was nonzero
16 Runtime error 129 ms 12152 KB Execution failed because the return code was nonzero
17 Runtime error 128 ms 12116 KB Execution failed because the return code was nonzero
18 Runtime error 129 ms 12184 KB Execution failed because the return code was nonzero
19 Runtime error 134 ms 12316 KB Execution failed because the return code was nonzero
20 Runtime error 126 ms 12056 KB Execution failed because the return code was nonzero
21 Runtime error 125 ms 12044 KB Execution failed because the return code was nonzero
22 Runtime error 125 ms 12248 KB Execution failed because the return code was nonzero
23 Runtime error 126 ms 12312 KB Execution failed because the return code was nonzero
24 Runtime error 124 ms 12132 KB Execution failed because the return code was nonzero
25 Runtime error 131 ms 12020 KB Execution failed because the return code was nonzero
26 Runtime error 136 ms 11964 KB Execution failed because the return code was nonzero
27 Runtime error 129 ms 11976 KB Execution failed because the return code was nonzero
28 Runtime error 131 ms 12216 KB Execution failed because the return code was nonzero
29 Runtime error 130 ms 11988 KB Execution failed because the return code was nonzero
30 Runtime error 141 ms 12112 KB Execution failed because the return code was nonzero
31 Runtime error 146 ms 12140 KB Execution failed because the return code was nonzero
32 Runtime error 132 ms 12028 KB Execution failed because the return code was nonzero