链接:https://www.nowcoder.com/acm/contest/206/B
来源:牛客网
题目描述
恬恬有一个nx n的数组。她在用这个数组玩游戏:
开始时,数组中每一个元素都是0。
恬恬会做某些操作。在一次操作中,她可以将某一行的所有元素同时加上一个值,也可以将某一列的所有元素同时加上一个值。
在几次操作后,一个元素被隐藏了。你能帮助她回忆隐藏的数是几吗?
输入描述:
第一行一个整数n(1≤ n≤ 1000)。
接下来n行每行n个整数表示数组a。
第(i+1)行的第j个元素表示aij(aij=-1或0≤ aij ≤ 10000)。-1表示隐藏的元素。
输出描述:
仅一个整数表示答案。
示例1
输入
复制
3
1 2 1
0 -1 0
0 1 0
输出
复制
1

有点坑这道题,一开始想了两个思路都判了好多秒才错,感觉差点什么特例没判,最后队友终于找出,差点自闭
思路就是每一行每一列依次删除每一行/列的最小值,隐藏数的那一行和列就不删,删到最后剩下就是隐藏数和所在的那一行和列,把行和列的数加起来就是隐藏数,然后坑点就是一开始直接加g[x][0] g[0][y] 没有考虑到如果隐藏数就是在0这个位置呢,就错了

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
const int N=1005;
int g[N][N];
int hang[N];
int lie[N];
int main(void){
   
    scanf("%d",&n);
    int x,y;
    for(int i=0;i<n;i++){
   
        int Min=0x3f3f3f3f;
        for(int j=0;j<n;j++){
   
            scanf("%d",&g[i][j]);
            if(g[i][j]==-1){
   
                x=i;
                y=j;
                continue;
            }
            Min=min(Min,g[i][j]);
        }
        hang[i]=Min;
    }
    for(int i=0;i<n;i++){
   
        bool flag=true;
        for(int j=0;j<n;j++){
   
            if(g[i][j]==-1){
   
                flag=false;
                break;
            }
        }
        if(flag){
   
            for(int j=0;j<n;j++){
   
                g[i][j]-=hang[i];
            }
        }
    }
    for(int j=0;j<n;j++){
   
        int Min=0x3f3f3f3f;
        for(int i=0;i<n;i++){
   
            Min=min(Min,g[i][j]);
        }
        bool flag=true;
        for(int i=0;i<n;i++){
   
            if(g[i][j]==-1){
   
                flag=false;
                break;
            }
        }
        if(flag){
   
            for(int i=0;i<n;i++){
   
                g[i][j]-=Min;
            }
        }
    }
    // for(int i=0;i<n;i++){
   
    // for(int j=0;j<n;j++){
   
    // printf("%d ",g[i][j]);
    // }
    // printf("\n");
    // }
    int fx=0;
    for(int j=0;j<n;j++){
   
        if(g[x][j]!=-1){
   
            fx=g[x][j];
            break;
        }
    }
    int fy=0;
    for(int i=0;i<n;i++){
   
        if(g[i][y]!=-1){
   
            fy=g[i][y];
            break;
        }
    }
    //printf("%d\n",g[x][0]+g[0][y]);
    printf("%d\n",fx+fy);
    return 0;
}