画棋盘
题目
小J和小R喜欢在课间玩井字棋。小R拿出一张 n×m 的纸，让小J指定哪些行和列需要画线，再由小R来画。小J想提前看到结果，于是请你暗中帮忙。
给定一个 n×m 的棋盘，在指定的行画横线，在指定的列画竖线。没有画线的格子用 0 表示，横线用 -，竖线用 |，交叉处用 +。
输入：第1行，整数 n、m、q、k，分别为行数、列数、画横线的行数、画竖线的列数。第2行，q 个整数表示画横线的行号。第3行，k 个整数表示画竖线的列号。
输出：输出 n 行 m 列的方阵，表示画线后的棋盘。
数据范围：n, m ≤ 1000，q, k ≤ 1,000,000。需要画线的行列在合法范围内，不保证不重复。
样例：
输入
5 5 2 2 1 3 4 5
输出
---++ 000|| ---++ 000|| 000||
思路
注意提示：n, m ≤ 1000，但 q, k 最大可达 1,000,000——输入的行列编号可能大量重复。因此用两个 bool 数组 rowLine[1001] 和 colLine[1001] 来记录哪些行/列需要画线。读入时直接 rowLine[行号] = true，不管重复多少次都只是反复标记同一个位置，不会浪费空间。
主逻辑是双重循环遍历每个格子 (i, j)，用 if-else 判断四种情况：rowLine[i] && colLine[j] 输出 +，只有 rowLine[i] 输出 -，只有 colLine[j] 输出 |，否则输出 0。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,q,k;
cin>>n>>m>>q>>k;
bool rowLine[1001]={false};
bool colLine[1001]={false};
for(int c=0;c<q;c++){
int row;
cin>>row;
rowLine[row]=true;
}
for(int c=0;c<k;c++){
int col;
cin>>col;
colLine[col]=true;
}
for(int c1=1;c1<=n;c1++){
for(int c2=1;c2<=m;c2++){
if(rowLine[c1]&&colLine[c2]){
cout<<"+";
}else if(rowLine[c1]){
cout<<"-";
}else if(colLine[c2]){
cout<<"|";
}else{
cout<<"0";
}
}
cout<<endl;
}
return 0;
}复杂度分析
- 时间复杂度：O(q + k + n×m)，读入标记各一次线性扫描，输出双重循环最多 1000×1000 = 10⁶ 次。
- 空间复杂度：O(n + m)，两个 bool 数组各长 1001。
看起来难的题，仔细分析也没那么难。关键是注意提示里的数据范围——q、k 最大百万，但行列数只有千级，所以用 bool 数组标记而不是逐个查找，把输入和输出完全分开处理。主逻辑只是 if-else 的四种组合，拆开来每一步都很清楚。