9月1日 拼多多 笔试

第一题

一个 n 阶矩阵，用米字线分割为如下8个区域。

矩阵元素需要满足：

• 各区域内的元素都等于区域的编号
• 被分割线穿过的元素值都等于0

打印这个矩阵。

示例用例：

输入：4
输出：
0 2 1 0
3 0 0 8
4 0 0 7
0 5 6 0

输入：5
输出：
0 2 0 1 0
3 0 0 0 8
0 0 0 0 0
4 0 0 0 7
0 5 0 6 0

我的代码

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    matrix:=make([][]int,n)
    for i:=0;i<n;i++{
        matrix[i]=make([]int,n)
    }
    for r:=0;r<(n+1)/2;r++{
        for c:=(n+1)/2;c<n-1-r;c++{
            matrix[r][c]=1
            matrix[r][n-1-c]=2
            matrix[n-1-c][r]=3
            matrix[c][r]=4
            matrix[n-1-r][n-1-c]=5
            matrix[n-1-r][c]=6
            matrix[c][n-1-r]=7
            matrix[n-1-c][n-1-r]=8
        }
    }
    for _,line:=range matrix{
        for _,e:=range line{
            fmt.Print(e," ")
        }
        fmt.Println()
    }
}

第二题

N*M 的矩阵，值为 1 表示一个士兵，0 表示没有士兵。相邻（上下左右）的士兵属于同一个队伍。
你可以将任意一个士兵移动到任意一个空的位置。求移动之后得到的最大队伍的人数。

用 bfs 找出每个连续的区域，并将该区域的每个点的值标记为 idx 并记录点的数量 cnt，将 idx 和 cnt 存进一个 map。

接下来，我们遍历所有非零的点，对于每一个点，我们访问他的相邻点，如果相邻点非零，那么我们可以在 map 中根据他的 idx 找到该区域的点的数量。将与该点相邻的区域的点数求和得 cnt。

如果与他相邻的区域的数量等于所有区域的数量，那么我们就从与该点相邻的区域从挪一点使得区域连通。单连通也没问题。

如果与他相邻的区域的数量小于所有区域的数量，那么我们就从其他区域从挪一点使得相邻区域连通，因此 cnt++。

所有非零点求得的 cnt 取最大值就是结果。

示例用例：

输入：
4 4
1 0 1 1
1 1 0 1
0 0 0 0
1 1 1 1
输出：
8

输入：
3 4
0 1 0 0
1 0 1 1
0 1 0 0
输出：
5

我的代码

#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <set>

using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    vector> grid(n);
    for (int i=0;i<n;i++){
        grid[i].resize(m);
        for (int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    map tps;
    int idx=10;
    int ans = 0;
    for (int i = 0; i != grid.size(); ++i)
        for (int j = 0; j != grid[0].size(); ++j) {
            int cur = 0;
            queue queuei;
            queue queuej;
            queuei.push(i);
            queuej.push(j);
            while (!queuei.empty()) {
                int cur_i = queuei.front(), cur_j = queuej.front();
                queuei.pop();
                queuej.pop();
                if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1)
                    continue;
                ++cur;
                grid[cur_i][cur_j] = idx;
                int di[4] = {0, 0, 1, -1};
                int dj[4] = {1, -1, 0, 0};
                for (int index = 0; index != 4; ++index) {
                    int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                    queuei.push(next_i);
                    queuej.push(next_j);
                }
            }
            if (cur){
                tps.emplace(idx++,cur);
            }
        }
    int max=0;
    for (int i = 0; i != grid.size(); ++i)
        for (int j = 0; j != grid[0].size(); ++j) {
            int cnt=0,total=0;
            if (!grid[i][j]){
                set ntps;
                if (i+1<grid.size()&&grid[i+1][j]){
                    ntps.insert(grid[i+1][j]);
                }
                if (i-1>=0&&grid[i-1][j]){
                    ntps.insert(grid[i-1][j]);
                }
                if (j+1<grid[0].size()&&grid[i][j+1]){
                    ntps.insert(grid[i][j+1]);
                }
                if (j-1>=0&&grid[i][j-1]){
                    ntps.insert(grid[i][j-1]);
                }
                for (int i:ntps)
                    total+=tps[i];
                if (ntps.size()<tps.size()){
                    total++;
                }
                if (total>max){
                    max=total;
                }
            }
        }
    cout<<max;
    return 0;
}