网易笔试20220317题解

第一题锯齿数独

判读该数独能否填完。

如果有多种填法就输出Multiple；

如果有一种就输出Unique并输出该种填法；

如果不能填完就输出No。

暴力回溯，注意每一行每一列也要满足数独要求。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y;
};

// int ans;
vector<string> ans_grid;
set<vector<string>>ans;//记录所有解法，set用来去重

bool check(vector<string> &grid, vector<vector<Node>> &pos) {
    
    //判断每个锯齿是否满足数独要求
    for(int i = 0; i < 3; i++) {
        vector<int>count(3);
        for(int j = 0; j < 3; j++) {
            if(isdigit(grid[pos[i][j].x][pos[i][j].y])) count[grid[pos[i][j].x][pos[i][j].y] - '1']++;
        }
        if(count[0] != 1 || count[1] != 1 || count[2] != 1) return false;
    }

    //判断每行是否满足数独要求
    for(int i = 0; i < 3; i++) {
        vector<int>count(3);
        for(int j = 0; j < 3; j++) {
            if(isdigit(grid[i][j])) count[grid[i][j] - '1']++;
        }
        if(count[0] != 1 || count[1] != 1 || count[2] != 1) return false;
    }

    //判断每列是否满足数独要求
    for(int i = 0; i < 3; i++) {
        vector<int>count(3);
        for(int j = 0; j < 3; j++) {
            if(isdigit(grid[j][i])) count[grid[j][i] - '1']++;
        }
        if(count[0] != 1 || count[1] != 1 || count[2] != 1) return false;
    }


    // for(auto &i: grid) cout << i << endl;
    //     cout << endl;
    return true;
}

void dfs(vector<string> &grid, vector<vector<Node>> &pos) {
    int x = -1, y = -1;
    //寻找下一个*，找不到x就等于-1
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(grid[i][j] == '*') {
                x = i, y = j;
                break;
            }
        }
        if(x != -1) break;
    }
    // cout << x << " " << y << endl;
    // cout << endl;
    if(x != -1) {//还有*没填
        grid[x][y] = '1';
        dfs(grid, pos);
        grid[x][y] = '2';
        dfs(grid, pos);
        grid[x][y] = '3';
        dfs(grid, pos);
        grid[x][y] = '*';
    } else {
        if(check(grid, pos)) {//填完了就检查是否满足要求
            ans.insert(grid);
            ans_grid = grid;
        }
    }
}

int main() {

    int T;
    cin >> T;
    while(T--) {
        vector<string>grid(3);
        for(int i = 0; i < 3; i++) cin >> grid[i];
        vector<vector<Node>>pos(3, vector<Node>(3));//记录三个锯齿
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                cin >> pos[i][j].x >> pos[i][j].y;
            }
        }
        // ans = 0;
        ans.clear();
        dfs(grid, pos, 0, 0);
        if(ans.size() == 1) {
            cout << "Unique" << endl;
            for(int i = 0; i < 3; i++) cout << ans_grid[i] << endl;
        } else if(ans.size() == 0) {
            cout << "No" << endl;
        } else {
            cout << "Multiple" << endl;
        }
    }


    return 0;
}

第二题黑白棋

黑白轮流下，每次判断八个方位中最远的异色棋位置，然后把中间的棋子颜色反转，并且一个棋子不能被连续两轮反转颜色。

直接模拟，注意只考虑连续的棋子，即中间不能有空位！！

#include <bits/stdc++.h>
using namespace std;

int dir[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};


int main() {

    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        vector<string>s(n);
        for(int i = 0; i < n; i++) cin >> s[i];
        vector<vector<bool>>last(n, vector<bool>(n, false));//记录上一轮哪些棋子动过
        char now = 'w';
        for(int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            // cout << endl;
            vector<vector<bool>>current(n, vector<bool>(n, false));//记录当前哪些棋子动过
            s[x][y] = now;
            // current[x][y] = true;
            for(int k = 0; k < 8; k++) {
                int far_x = -1, far_y = -1;
                int cur_x = x + dir[k][0], cur_y = y + dir[k][1];
                while(cur_x >= 0 && cur_x < n && cur_y >= 0 && cur_y < n) {//找到最远的异色棋子位置
                    if(s[cur_x][cur_y] == '-') break;//注意中间不能有空位！！
                    if(s[cur_x][cur_y] != now) {
                        far_x = cur_x;
                        far_y = cur_y;
                    }
                    cur_x += dir[k][0];
                    cur_y += dir[k][1];
                }
                if(far_x != -1) {//没有异色棋子
                    // cout << far_x << far_y << endl;
                    cur_x = x + dir[k][0];
                    cur_y = y + dir[k][1];
                    while(cur_x >= 0 && cur_x < n && cur_y >= 0 && cur_y < n) {
                        if(cur_x == far_x && cur_y == far_y) break;
                        if(!last[cur_x][cur_y]) {//如果上一轮没有动过颜色，就反转颜色
                            if(s[cur_x][cur_y] != '-') {
                                last[cur_x][cur_y] = true;
                                current[cur_x][cur_y] = true;
                                if(s[cur_x][cur_y] == 'w') s[cur_x][cur_y] = 'b';
                                else if(s[cur_x][cur_y] == 'b') s[cur_x][cur_y] = 'w';
                            }
                        }
                        cur_x += dir[k][0];
                        cur_y += dir[k][1];
                    }
                }
            }
            last = current;
            if(now == 'w') now = 'b';
            else now = 'w';
            for(int i = 0; i < n; i++) cout << s[i] << endl;
            cout << endl << endl;
        }
        for(int i = 0; i < n; i++) cout << s[i] << endl;
        cout << "END" << endl;

    }

    return 0;
}

第三题消灭敌人

给定地图有a个人消灭b个敌人，第i个人每次可以走v[i]步，不能穿过墙和敌人，除非最后一步是敌人（最后一步是敌人就消灭）。求消灭所有敌人最短步数。

还是准备暴力搜索，结果超时，无解

#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

struct Node {
    int x, y, step;
    Node() {
        step = 0;
    }
};

int ans;
bool vis[11][21][21];
int n, m, a, b;

void dfs(vector<string> &s, vector<int> &v, int b, int step, vector<Node> &person, int index) {
    if(b == 0) {
        ans = min(ans, step);
        return;
    }
    if(step >= ans) return;
    if(index != -1) {
        int i = index;
        for(int k = 0; k < 4; k++) {
            int next_x = person[i].x + dir[k][0];
            int next_y = person[i].y + dir[k][1];
            if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && s[next_x][next_y] != 'W' && !vis[i][next_x][next_y]) {
                vis[i][next_x][next_y] = true;
                int pre_x = person[i].x;
                int pre_y = person[i].y;
                person[i].x = next_x;
                person[i].y = next_y;
                person[i].step++;

                int next_b = b;
                if(s[next_x][next_y] == 'E' && person[i].step % v[i] == 0) {
                    next_b--;
                    s[next_x][next_y] = '+';
                }
                if(person[i].step % v[i] == 0) {
                    dfs(s, v, next_b, step + 1, person, -1);
                } else {
                    dfs(s, v, next_b, step + 1, person, index);
                }

                person[i].step--;

                if(next_b != b) {
                    s[next_x][next_y] = 'E';
                }
                person[i].x = pre_x;
                person[i].y = pre_y;
                vis[i][next_x][next_y] = false;
            }
        }
    }
    for(int i = 0; i < a; i++) {
        for(int k = 0; k < 4; k++) {
            int next_x = person[i].x + dir[k][0];
            int next_y = person[i].y + dir[k][1];
            if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && s[next_x][next_y] != 'W' && !vis[i][next_x][next_y]) {
                vis[i][next_x][next_y] = true;
                int pre_x = person[i].x;
                int pre_y = person[i].y;
                person[i].x = next_x;
                person[i].y = next_y;
                person[i].step++;

                int next_b = b;
                if(s[next_x][next_y] == 'E' && person[i].step % v[i] == 0) {
                    next_b--;
                    s[next_x][next_y] = '+';
                }
                if(person[i].step % v[i] == 0) {
                    dfs(s, v, next_b, step + 1, person, -1);
                } else {
                    dfs(s, v, next_b, step + 1, person, i);
                }
                person[i].step--;

                if(next_b != b) {
                    s[next_x][next_y] = 'E';
                }
                person[i].x = pre_x;
                person[i].y = pre_y;
                vis[i][next_x][next_y] = false;
            }
        }
    }
}

int main() {

    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m >> a >> b;
        vector<int>v(a);
        for(int i = 0; i < a; i++) {
            cin >> v[i];
        }
        vector<string>s(n);
        vector<Node>person(a);
        memset(vis, false, sizeof(vis));

        for(int i = 0; i < n; i++) {
            cin >> s[i];
            for(int j = 0; j < s[i].size(); j++) {
                if(isdigit(s[i][j])) {
                    person[s[i][j] - '0'].x = i;
                    person[s[i][j] - '0'].y = j;
                    vis[s[i][j] - '0'][i][j] = true;
                }
            }
        }
        ans = INT_MAX;
        dfs(s, v, b, 0, person, -1);
        if(ans == INT_MAX) cout << -1 << endl;
        else cout << ans << endl;
    }

    return 0;
}

/*

2
1 10 1 1
4
0++++E++++
4 4 2 2
4 4
0++1
EWW+
+WW+
+E++
*/

#网易笔试##笔经##网易#