제출 #663377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
663377		bluebird	Tracks in the Snow (BOI13_tracks)	Java	0 / 100	146 ms	12420 KiB

tracks

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
• Subtask 2: 0 / 70