2020年米哈游秋季招聘程序 B卷编程题

消消乐

题目描述

某消除类的游戏，玩家每次操作可以将相邻的图形进行交换，如果交换后出现三个以上的连续图形时，这些图形就会消失
图形消失后，同一列上面的图形会往下掉。最上方的位置为空
现给定一个初始稳定的局面和一次交换操作，请计算此次操作能消除多少图形

示例

输出
4 4
HFCE
GCAC
GFAD
DCBA
3 2 3 3
输出
3
输入
4 4
0F0E
0CAC
GFAD
AABA
3 2 3 3
输出
5

代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
    private static Queue<Integer> queue = new LinkedList<>();
    private static void move(char[][] map, int x, int y, int len) {
        for(int i = x; i >= len; --i) {
            map[i][y] = map[i - len][y];
            queue.add(i*100+y);
        }
        for(int i = len-1; i >= 0; --i)
            map[i][y] = '0';
    }
    private static void move2(char[][] map, int x, int y, int len, int flag, int tx, int ty) {
        for(int i = 0; i < len; ++i) {
            if(x == tx && y+i == ty && flag > 2);
            else move(map, x, y + i, 1);
        }
    }
    private static void modify(char[][] map, int x, int y) {
        if(map[x][y] == '0') return;
        // 上下
        int tx1 = x, ty = y, len1 = 1;
        for(int i = x-1; i >= 0; --i) {
            if(map[i][y] == map[x][y])
                ++len1;
            else break;
        }
        for(int i = x+1; i < map.length; ++i) {
            if(map[i][y] == map[x][y]) {
                ++len1;
                tx1 = Math.max(tx1, i);
            } else break;
        }

        // 左右
        int tx2 = x, ty2 = y, len2 = 1;
        for(int i = y-1; i >= 0; --i) {
            if(map[x][i] == map[x][y]) {
                ++len2;
                ty2 = Math.min(ty2, i);
            } else break;
        }
        for(int i = y+1; i < map[0].length; ++i) {
            if (map[x][i] == map[x][y]) {
                ++len2;
            } else break;
        }
        if(len1 > 2) move(map, tx1, ty, len1);
        if(len2 > 2) move2(map, tx2, ty2, len2, len1, x, y);
    }
    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        int r = sca.nextInt(), c = sca.nextInt();
        char[][] map = new char[r][c];
        int cnt = 0;
        for(int i = 0; i < r; ++i) {
            String str = sca.next();
            for(int j = 0; j < str.length(); ++j) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == '0')
                    ++cnt;
            }
        }
        int r1 = sca.nextInt(), c1 = sca.nextInt(), r2 = sca.nextInt(), c2 = sca.nextInt();
        char tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
        queue.offer(r1*100+c1);
        queue.offer(r2*100+c2);
        while(!queue.isEmpty()) {
            int x = queue.peek()/100, y = queue.poll()%100;
            modify(map, x, y);
        }
        int newCnt = 0;
        for(char[] rr : map)
            for(char cc : rr) {
                if(cc == '0')
                    ++newCnt;
            }
        System.out.println(newCnt-cnt);
    }
}