欢迎访问==> 【考研OR保研】机试题
题目描述
有一个特殊的 $n$ 行 $m$ 列的矩阵 $A_{ij}$,每个元素都是正整数,每一行和每一列都是独立的等差数列。
在某一次故障中,这个矩阵的某些元素的真实值丢失了,被重置为 $0$。
现在需要你想办法恢复这些元素,并且按照行号和列号从小到大的顺序(行号为第一关键字,列号为第二关键字,从小到大)输出能够恢复的元素。
输入格式
输入的第一行包含两个正整数 $n$ 和 $m$。
接下来 $n$ 行,每行 $m$ 个整数,表示整个矩阵,如果 $A_{ij}$ 大于 $0$,则表示真实值存在的元素。如果 $A_{ij}$ 等于 $0$,表示真实值丢失的元素。
输出格式
输出若干行,表示所有能够恢复的元素。每行三个整数 $i,j,x$,表示 $A_{ij}$ 的真实值是 $x$。
矩阵左上角的元素为 $A_{11}$,右下角的元素为 $A_{nm}$。
数据范围
$1 \\le n,m \\le 10^3$,
$1 \\le A_{ij} \\le 10^9$
输入样例:
3 4
1 2 0 0
0 0 0 0
3 0 0 0
输出样例:
1 3 3
1 4 4
2 1 2
样例解释
可以恢复 $3$ 个元素,$A_{13}$ 的真实值是 $3$,$A_{14}$ 的真实值是 $4$,$A_{21}$ 的真实值是 $2$。
C++ 代码
/*
由于是等差数列,所以每行或者每列知道了两个数便可以将整行或者整列求出来了
*/
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1010, M = 2 * N;
vector<pii> res, p[M];
int n, m, g[N][N], cnt[M];
bool st[M]; //行是1 ~ n, 列是 n + 1 ~ n + m;
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
scanf("%d", &g[i][j]);
if(g[i][j])
{
cnt[i] ++, cnt[j + n] ++; //记录这一行和这一列有多少数已经知道了
p[i].push_back({j, g[i][j]}); //记录这一行知道了哪一列的什么数
p[j + n].push_back({i, g[i][j]}); //记录这一列知道了哪一行的什么数
}
}
}
queue<int> q;
for(int i = 1; i <= n; i ++) // 行
{
if(cnt[i] >= 2 && cnt[i] < m) //cnt[i] > 2说明能算,cnt[i] < m说明有缺失的元素
{
q.push(i); //将这一行加入队列
st[i] = true;
}
}
for(int i = n + 1; i <= n + m; i ++) //列
{
if(cnt[i] >= 2 && cnt[i] < n) //cnt[i] > 2说明能算,cnt[i] < n说明有缺失的元素
{
q.push(i); //将这一列加入队列
st[i] = true;
}
}
while(q.size()) //进行BFS
{
int t = q.front();
q.pop();
if(t <= n) //说明是行
{
int d = (p[t][1].y - p[t][0].y) / (p[t][1].x - p[t][0].x); //计算公差
int a = p[t][1].y - d * p[t][1].x; //计算初值
for(int i = 1; i <= m; i ++) //知道了公差和初值,这一行的每列都可以算出来
{
if(!g[t][i]) //第t行的第i列还没算出来,将第i列通过等差公式算出来
{
res.push_back({t, i}); //记录答案
g[t][i] = a + i * d; //计算g[t][i]的值
cnt[i + n] ++; //这一列的cnt++
p[i + n].push_back({t, g[t][i]}); //这一列多了一个值
//cnt[i + n] > 2说明能算了,cnt[i + n] < n说明有缺失的元素
//如果还没加入队列,将这一列加入队列
if(cnt[i + n] >= 2 && cnt[i + n] < n && !st[i + n])
{
q.push(i + n);
st[i + n] = true;
}
}
}
}
else //列同行,可参考上边行的处理
{
int d = (p[t][1].y - p[t][0].y) / (p[t][1].x - p[t][0].x);
int a = p[t][1].y - d * p[t][1].x;
t = t - n;
for(int i = 1; i <= n; i ++)
{
if(!g[i][t])
{
res.push_back({i, t});
g[i][t] = a + i * d;
cnt[i] ++;
p[i].push_back({t, g[i][t]});
if(cnt[i] >= 2 && cnt[i] < m && !st[i])
{
q.push(i);
st[i] = true;
}
}
}
}
}
sort(res.begin(), res.end());
for(int i = 0; i < res.size(); i ++)
{
pii t = res[i];
printf("%d %d %d\n", t.x, t.y, g[t.x][t.y]);
}
return 0;
}