oj.uz

답안 #663377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
663377 2022-11-26T20:30:03 Z bluebird Tracks in the Snow (BOI13_tracks) Java 11
0 / 100
 146 ms 12420 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.println(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 131 ms 12124 KB Execution failed because the return code was nonzero
2 Runtime error 129 ms 11964 KB Execution failed because the return code was nonzero
3 Runtime error 124 ms 12420 KB Execution failed because the return code was nonzero
4 Runtime error 127 ms 12336 KB Execution failed because the return code was nonzero
5 Runtime error 128 ms 12052 KB Execution failed because the return code was nonzero
6 Runtime error 130 ms 12096 KB Execution failed because the return code was nonzero
7 Runtime error 129 ms 12240 KB Execution failed because the return code was nonzero
8 Runtime error 129 ms 12252 KB Execution failed because the return code was nonzero
9 Runtime error 130 ms 11832 KB Execution failed because the return code was nonzero
10 Runtime error 129 ms 12340 KB Execution failed because the return code was nonzero
11 Runtime error 125 ms 11964 KB Execution failed because the return code was nonzero
12 Runtime error 126 ms 11964 KB Execution failed because the return code was nonzero
13 Runtime error 131 ms 12120 KB Execution failed because the return code was nonzero
14 Runtime error 130 ms 12112 KB Execution failed because the return code was nonzero
15 Runtime error 131 ms 12328 KB Execution failed because the return code was nonzero
16 Runtime error 128 ms 12160 KB Execution failed because the return code was nonzero
17 Runtime error 130 ms 11852 KB Execution failed because the return code was nonzero
18 Runtime error 129 ms 12160 KB Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 132 ms 11988 KB Execution failed because the return code was nonzero
2 Runtime error 146 ms 12156 KB Execution failed because the return code was nonzero
3 Runtime error 127 ms 12232 KB Execution failed because the return code was nonzero
4 Runtime error 129 ms 11900 KB Execution failed because the return code was nonzero
5 Runtime error 131 ms 12300 KB Execution failed because the return code was nonzero
6 Runtime error 131 ms 12064 KB Execution failed because the return code was nonzero
7 Runtime error 132 ms 12000 KB Execution failed because the return code was nonzero
8 Runtime error 127 ms 12132 KB Execution failed because the return code was nonzero
9 Runtime error 129 ms 12312 KB Execution failed because the return code was nonzero
10 Runtime error 128 ms 12156 KB Execution failed because the return code was nonzero
11 Runtime error 129 ms 12056 KB Execution failed because the return code was nonzero
12 Runtime error 127 ms 12284 KB Execution failed because the return code was nonzero
13 Runtime error 126 ms 12368 KB Execution failed because the return code was nonzero
14 Runtime error 133 ms 11948 KB Execution failed because the return code was nonzero
15 Runtime error 129 ms 12260 KB Execution failed because the return code was nonzero
16 Runtime error 131 ms 12128 KB Execution failed because the return code was nonzero
17 Runtime error 128 ms 12220 KB Execution failed because the return code was nonzero
18 Runtime error 127 ms 12096 KB Execution failed because the return code was nonzero
19 Runtime error 133 ms 11948 KB Execution failed because the return code was nonzero
20 Runtime error 128 ms 12000 KB Execution failed because the return code was nonzero
21 Runtime error 131 ms 12220 KB Execution failed because the return code was nonzero
22 Runtime error 129 ms 11988 KB Execution failed because the return code was nonzero
23 Runtime error 128 ms 12292 KB Execution failed because the return code was nonzero
24 Runtime error 131 ms 12096 KB Execution failed because the return code was nonzero
25 Runtime error 140 ms 11956 KB Execution failed because the return code was nonzero
26 Runtime error 128 ms 12276 KB Execution failed because the return code was nonzero
27 Runtime error 131 ms 11964 KB Execution failed because the return code was nonzero
28 Runtime error 134 ms 12152 KB Execution failed because the return code was nonzero
29 Runtime error 128 ms 12180 KB Execution failed because the return code was nonzero
30 Runtime error 128 ms 12228 KB Execution failed because the return code was nonzero
31 Runtime error 135 ms 11924 KB Execution failed because the return code was nonzero
32 Runtime error 132 ms 12232 KB Execution failed because the return code was nonzero