网易互娱 8.27 笔试题解
第三题真恶心，全枚举了一遍踩点完成
// 第1题
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int T;
while (cin >> T) {
int N, M;
for (int t = 0; t < T; ++t) {
cin >> N >> M;
vector<vector<char>> v(N, vector<char>(N));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) cin >> v[i][j];
}
if (M <= N) {
int idx = (N - M) / 2;
for (int i = idx; i < N - idx; ++i) {
for (int j = idx; j < N - idx; ++j) {
cout << v[i][j];
}
cout << endl;
}
if (t != T - 1) cout << endl;
} else {
float left = (float(M - N)) / 2 / N;
int times = ceil(left) * 2 + 1;
times *= N;
vector<vector<char>> wall(times, vector<char>(times));
for (int i = 0; i < times; ++i) {
for (int j = 0; j < times; ++j) {
wall[i][j] = v[i%N][j%N];
}
}
int center = ceil(times / 2);
int width = ceil(M / 2);
for (int i = center - width; i <= center + width; ++i) {
for (int j = center - width; j <= center + width; ++j) {
cout << wall[i][j];
}
cout << endl;
}
if (t != T - 1) cout << endl;
}
}
}
return 0;
}
// 第2题
#include <iostream>
#include <vector>
#include <set>
using namespace std;
bool is_intersect(const vector<int>& a, const vector<int>& b) {
int xmin = max(a[0], b[0]);
int xmax = min(a[2], b[2]);
int ymin = max(a[1], b[1]);
int ymax = min(a[3], b[3]);
return (xmin < xmax && ymin < ymax);
}
int main() {
int T;
while (cin >> T) {
int N;
for (int t = 0; t < T; ++t) {
cin >> N;
vector<vector<int>> v;
int x0, y0, x1, y1;
for (int i = 0; i < N; ++i) {
cin >> x0 >> y0 >> x1 >> y1;
v.push_back({x0, y0, x1, y1});
}
if (N == 1) {
cout << 0;
if (t != T - 1) cout << endl;
continue;
}
set<vector<int>> ss;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
if (is_intersect(v[i], v[j])) {
ss.emplace(v[i]);
ss.emplace(v[j]);
}
}
}
if (ss.empty()) {
cout << 0;
if (t != T - 1) cout << endl;
continue;
}
int res = 0;
vector<vector<int>> grid(1005, vector<int>(1005, 0));
for (auto it = ss.begin(); it != ss.end(); ++it) {
for (int i = (*it)[0]; i < (*it)[2]; ++i) {
for (int j = (*it)[1]; j < (*it)[3]; ++j) {
if (grid[i][j] == 0) {
++res;
}
grid[i][j] = 1;
}
}
}
cout << res;
if (t != T - 1) cout << endl;
}
}
return 0;
}
// 第3题
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// 构造 string，24位可以用int，用哈希表缓存
/*
- -
|\/|/\|
- -
|\/|\/|
_ _
前8位代表边框，后12位代表内部，还有8位是陡的斜线
*/
int connect(int x, int y, int nx, int ny) {
if (x < nx) {
swap(x, nx);
swap(y, ny);
}
if (x == 0) {
if (y == 0) {
if (nx == 0 && ny == 1) return (1 << 1);
else if (nx == 0 && ny == 2) return (1 << 1) | (1 << 2);
else if (nx == 1 && ny == 0) return (1 << 8);
else if (nx == 2 && ny == 0) return (1 << 7) | (1 << 8);
else if (nx == 1 && ny == 1) return (1 << 9);
else if (nx == 1 && ny == 2) return (1 << 17);
else if (nx == 2 && ny == 1) return (1 << 24);
else if (nx == 2 && ny == 2) return (1 << 9) | (1 << 13);
} else if (y == 1) {
if (nx == 0 && ny == 0) return (1 << 1);
else if (nx == 0 && ny == 2) return (1 << 2);
else if (nx == 1 && ny == 0) return (1 << 28);
else if (nx == 1 && ny == 1) return (1 << 10);
else if (nx == 1 && ny == 2) return (1 << 25);
else if (nx == 2 && ny == 0) return (1 << 18);
else if (nx == 2 && ny == 1) return (1 << 10) | (1 << 14);
else if (nx == 2 && ny == 2) return (1 << 19);
} else if (y == 2) {
if (nx == 0 && ny == 0) return (1 << 1) | (1 << 2);
else if (nx == 0 && ny == 1) return (1 << 2);
else if (nx == 1 && ny == 0) return (1 << 20);
else if (nx == 1 && ny == 1) return (1 << 11);
else if (nx == 1 && ny == 2) return (1 << 3);
else if (nx == 2 && ny == 0) return (1 << 11) | (1 << 15);
else if (nx == 2 && ny == 1) return (1 << 21);
else if (nx == 2 && ny == 2) return (1<<3) | (1<<4);
}
} else if (x == 1) {
if (y == 0) {
if (nx == 0 && ny == 0) return (1 << 8);
else if (nx == 0 && ny == 1) return (1 << 28);
else if (nx == 0 && ny == 2) return (1 << 20);
else if (nx == 1 && ny == 1) return (1 << 16);
else if (nx == 1 && ny == 2) return (1 << 12) | (1 << 16);
else if (nx == 2 && ny == 0) return (1 << 7);
else if (nx == 2 && ny == 1) return (1 << 27);
else if (nx == 2 && ny == 2) return (1 << 23);
} else if (y == 1) {
if (nx == 0 && ny == 0) return (1 << 9);
else if (nx == 0 && ny == 1) return (1 << 10);
else if (nx == 0 && ny == 2) return (1 << 11);
else if (nx == 1 && ny == 0) return (1 << 16);
else if (nx == 1 && ny == 2) return (1 << 12);
else if (nx == 2 && ny == 0) return (1 << 15);
else if (nx == 2 && ny == 1) return (1 << 14);
else if (nx == 2 && ny == 2) return (1 << 13);
} else if (y == 2) {
if (nx == 0 && ny == 0) return (1 << 17);
else if (nx == 0 && ny == 1) return (1 << 25);
else if (nx == 0 && ny == 2) return (1 << 3);
else if (nx == 1 && ny == 0) return (1 << 16) | (1 << 12);
else if (nx == 1 && ny == 1) return (1 << 12);
else if (nx == 2 && ny == 0) return (1 << 22);
else if (nx == 2 && ny == 1) return (1 << 26);
else if (nx == 2 && ny == 2) return (1 << 4);
}
} else {
if (y == 0) {
if (nx == 0 && ny == 0) return (1 << 7) | (1 << 8);
else if (nx == 0 && ny == 1) return (1 << 18);
else if (nx == 0 && ny == 2) return (1 << 15) | (1 << 11);
else if (nx == 1 && ny == 0) return (1 << 7);
else if (nx == 1 && ny == 1) return (1 << 15);
else if (nx == 1 && ny == 2) return (1 << 22);
else if (nx == 2 && ny == 1) return (1 << 6);
else if (nx == 2 && ny == 2) return (1 << 5) | (1 << 6);
} else if (y == 1) {
if (nx == 0 && ny == 0) return (1 << 24);
else if (nx == 0 && ny == 1) return (1 << 10) | (1 << 14);
else if (nx == 0 && ny == 2) return (1 << 21);
else if (nx == 1 && ny == 0) return (1 << 27);
else if (nx == 1 && ny == 1) return (1 << 14);
else if (nx == 1 && ny == 2) return (1 << 26);
else if (nx == 2 && ny == 0) return (1 << 6);
else if (nx == 2 && ny == 2) return (1 << 5);
} else if (y == 2) {
if (nx == 0 && ny == 0) return (1 << 9) | (1 << 13);
else if (nx == 0 && ny == 1) return (1 << 19);
else if (nx == 0 && ny == 2) return (1 << 3) | (1 << 4);
else if (nx == 1 && ny == 0) return (1 << 23);
else if (nx == 1 && ny == 1) return (1 << 13);
else if (nx == 1 && ny == 2) return (1 << 4);
else if (nx == 2 && ny == 1) return (1 << 5);
else if (nx == 2 && ny == 0) return (1 << 5) | (1 << 6);
}
}
return 0;
}
void dfs(int x, int y, int cur, vector<vector<char>> &grid, unordered_set<int> &ss) {
grid[x][y] = 'X';
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (grid[i][j] == '.') {
int val = connect(x, y, i, j);
int nex = cur | val;
ss.emplace(nex);
dfs(i, j, nex, grid, ss);
}
}
}
grid[x][y] = '.';
}
int main() {
int T;
while (cin >> T) {
for (int t = 0; t < T; ++t) {
vector<vector<char>> v(3, vector<char>(3));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) cin >> v[i][j];
}
unordered_set<int> ss;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (v[i][j] == '.') dfs(i, j, 0, v, ss);
}
}
cout << ss.size();
if (t != T - 1) cout << endl;
}
}
return 0;
} 
膜拜大佬
拼多多主管面17人在聊