阿里第二题思路简单,但是写起来很复杂,需要多个数组保存变量
反正我是写完就剩10分钟了,提交一直出现边界溢出的错误,找也找不到哪里的问题?有大佬帮忙看看吗
#include <bits/stdc++.h>
using namespace std;
int n,m,q;
int temp;
int i,j;
int x,y;
vector<pair<int,int> >vp;//输入的查询的数据
vector<vector<int> >vvi;//输入的数组
vector<vector<int > > vvp1,vvp2;//分别保存行和列不为0的坐标
vector<bool> visited1,visited2;//判断是否填充了某一行
bool fillRow(){
bool ret = false;
for(i=0;i<n;++i){
if(vvp1[i].size() > 1 && !visited1[i]){
visited1[i] = true;
ret =true;
x = vvp1[i][0];
y = vvp1[i][1];
if(x>y) swap(x,y);
temp = (vvi[i][y] - vvi[i][x])/(y-x);
if(vvi[i][0] == 0) vvp2[0].push_back(i);
vvi[i][0] = vvi[i][x]-(x-0)*temp;
for(j=1;j<m;++j){
if(vvi[i][j] == 0){
vvp2[j].push_back(i);
vvi[i][j] = vvi[i][j-1]+temp;
}
}
}
}
return ret;
}
bool fillCol(){
bool ret = false;
for(j=0;j<m;++j){
if(vvp2[j].size() > 1 && !visited2[j]){
visited2[j] = true;
ret = true;
x = vvp2[j][0];
y = vvp2[j][1];
if(x>y)swap(x,y);
temp = (vvi[y][j] - vvi[x][j])/(y-x);
if(vvi[0][j] == 0) vvp1[0].push_back(j);
vvi[j][0] = vvi[x][j]-(x-0)*temp;
for(i=1;i<n;++i){
if(vvi[i][j] == 0){
vvp1[i].push_back(j);
vvi[i][j] = vvi[i-1][j]+temp;
}
}
}
}
return ret;
}
int main(){
scanf("%d %d %d",&n,&m,&q);
vp.resize(q);
visited1.resize(n,false); visited2.resize(m,false);
vvi.resize(n,vector<int>(m));
vvp1.resize(n),vvp2.resize(m);
for(i=0;i<n;++i){
for(j=0;j<m;++j){
scanf("%d",&vvi[i][j]);
if(vvi[i][j]!=0){
vvp1[i].push_back(j);
vvp2[j].push_back(i);
}
}
}
for(i=0;i<q;++i){
scanf("%d %d",&temp,&j);
vp[i] = {temp,j}; // x y
}
while(fillRow() || fillCol()){
}
for(i=0;i<q;++i){
x = vp[i].first,y=vp[i].second;
if(vvi[x][y] == 0){
printf("Unknown\n");
}else{
printf("%d\n",vvi[x][y]);
}
}
return 0;
}#阿里巴巴##笔试题目#
查看7道真题和解析