变身程序员-头条笔试题2019

Unimen 2020-05-25

变身程序员-头条笔试题2019

公司的程序员不够用了,决定把产品经理都转变为程序员以解决开发时间长的问题。

在给定的矩形网格中,每个单元格可以有以下三个值之一:

  • 值0代表空单元格;
  • 值1代表产品经理;
  • 值2代表程序员;

每分钟,任何与程序员(在4个正方向上)相邻的产品经理都会变成程序员。

返回直到单元格中没有产品经理为止所必须经过的最小分钟数。

如果不可能,返回-1。

以下是一个4分钟转变完成的示例:

2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
1 1 0  ->  2 1 0  ->  2 2 0  ->  2 2 0  ->  2 2 0
0 1 1      0 1 1      0 1 1      0 2 1      0 2 2

输入格式

不固定多行(行数不超过10),毎行是按照空格分割的数字(不固定,毎行数字个数不超过10)。

其中每个数组项的取值仅为0、1、2三种。

读取时可以按行读取,直到读取到空行为止,再对读取的所有行做转换处理。

输出格式

如果能够将所有产品经理变成程序员,则输出最小的分钟数。

如果不能够将所有的产品经理变成程序员,则返回-1.

输入样例1:

0 2
1 0

输出样例1:

-1

输入样例2:

1 2 1
1 1 0
0 1 1

输出样例2:

3

输入样例3:

1 2
2 1
1 2
0 1
0 1
1 1

输出样例3:

4

语法点:Scanner 读入数据时,hasNextLine() 判断是否还有数据需要读入,nextLine() 读取一行数据为字符串。

解题思路:判断1周围是否有2存在,如果有将其变成2‘,但需要注意区分当前轮才变成2‘的不能算,因此需要特殊处理区分当前才变成2‘的和之前变成2的。直到遍历一轮没有进行任何操作,结束遍历。此时如果还有1存在返回-1,否则返回有效遍历的轮次(此轮有将1变成2,则该轮次有效)。

题目没有明确数据规模大小,因此推测数据量较小,模拟即可。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<int[]> g = new ArrayList<>();
        int[] dx = new int[] {1,-1,0,0}, dy = new int[] {0,0,1,-1};
        while(sc.hasNextLine()) {
            String[] strs = sc.nextLine().split(" ");
            int[] tmp = new int[strs.length];
            for(int i=0; i < strs.length; i++)
                tmp[i] = Integer.valueOf(strs[i]);
            g.add(tmp);
        }
        int m = g.size(), n = g.get(0).length;
        int times = 0;
        while(true)  {
            boolean change = false;
            for(int i=0; i < m; i++) {
                for(int j=0; j < n; j++) {
                    if(g.get(i)[j] == 1) {
                        for(int k=0; k < 4; k++) {
                            int x = i + dx[k], y = j + dy[k];
                            if(x >= 0  && x < m && y >= 0 && y < n && g.get(x)[y] > 1 
                               && g.get(x)[y] < times+3) {
                                g.get(i)[j] = times + 3;
                                change = true;
                                break;
                            }
                        }
                    }
                }
            }
            if(change) times++;
            else break;
            //System.out.println(times);
        }
        for(int i=0; i < m; i++) 
            for(int j=0; j < n; j++) 
                if(g.get(i)[j] == 1) times = -1;
        System.out.println(times);
    }
}

相关推荐