网易笔试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++
*/ 
