1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include <queue> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAXN 1010
int n,m,a[MAXN][MAXN]; vector<pair<int,int> >r[MAXN],c[MAXN]; vector<pair<pair<int,int>,int> >ans; bool use[2][MAXN]; queue<pair<bool,int> >q;
int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { scanf("%d",&a[i][j]); if(a[i][j]) { r[i].push_back(make_pair(j,a[i][j])); c[j].push_back(make_pair(i,a[i][j])); } } for(int i=1;i<=n;++i) if(r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true; for(int j=1;j<=m;++j) if(c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true; while(!q.empty()) { pair<int,int> tmp=q.front(); q.pop(); if(!tmp.first) { int i=tmp.second; int step=(r[i][1].second-r[i][0].second)/(r[i][1].first-r[i][0].first); for(int j=1;j<=m;++j) if(!a[i][j]) { a[i][j]=r[i][0].second+step*(j-r[i][0].first); ans.push_back(make_pair(make_pair(i,j),a[i][j])); r[i].push_back(make_pair(j,a[i][j])); c[j].push_back(make_pair(i,a[i][j])); if(!use[0][i]&&r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true; if(!use[1][j]&&c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true; } } else { int j=tmp.second; int step=(c[j][1].second-c[j][0].second)/(c[j][1].first-c[j][0].first); for(int i=1;i<=n;++i) if(!a[i][j]) { a[i][j]=c[j][0].second+step*(i-c[j][0].first); ans.push_back(make_pair(make_pair(i,j),a[i][j])); r[i].push_back(make_pair(j,a[i][j])); c[j].push_back(make_pair(i,a[i][j])); if(!use[0][i]&&r[i].size()>1) q.push(make_pair(0,i)),use[0][i]=true; if(!use[1][j]&&c[j].size()>1) q.push(make_pair(1,j)),use[1][j]=true; } } } sort(ans.begin(),ans.end()); for(auto it:ans) printf("%d %d %d\n",it.first.first, it.first.second, it.second); return 0; }
|