読者です 読者をやめる 読者になる 読者になる

AOJ 1117 Missing Numbers

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1117

所々、虫食いになってる表が与えられるからそれを埋める。

解法

一カ所だけ?の行(列)なら埋められる。

コード

int p, s;
char row[10];
int a[128][128], b[128][128];

int main(){
  bool outf = 0;
  while(scanf("%d", &p) && p){
    scanf("%d", &s);
    rep(i, 128) rep(j, 128) a[i][j] = INF;
    memset(b, 0, sizeof(b));
    rep(i, p+1) rep(j, s+1){
      scanf("%s", row);
      if(row[0] == '?'){
    b[i][j] = -1;
    continue;
      }
      a[i][j] = atoi(row);
    }

   int c, sum, point;
    bool f = true;
    while(f){
      f = false;
      rep(i, p){
    c = 0;
    rep(j, s) if(a[i][j] == INF){ c++; point = j;}
    if(c != 1) continue;
    f = 1;
    sum = 0;
    rep(j, s) if(a[i][j] != INF) sum += a[i][j];
    a[i][point] = a[i][s] - sum;
      }
      rep(j, s){
    c = 0;
    rep(i, p) if(a[i][j] == INF){ c++; point = i;}
    if(c != 1) continue;
    f = 1;
    sum = 0;
    rep(i, p) if(a[i][j] != INF) sum += a[i][j];
    a[point][j] = a[p][j] - sum;
      }
    }
    if(outf){
      puts("");
    }
    outf = 1;
    rep(i, p) rep(j, s) if(a[i][j] == INF) f = 1;
    if(f){
      puts("NO");
    }else{
      rep(i, p) rep(j, s) if(b[i][j] == -1) printf("%d\n", a[i][j]);
    }

  }
  return 0;
}

フラグ使いまくりで汚いコードになってる。行列それぞれの?の数を配列に記憶しておくと無駄なループがなくなって計算量が落とせる