Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2422-db2d8ba9
この記事にトラックバックする(FC2ブログユーザー)

Round #209 DIV2 A問題 - Table (この記事を編集する[管理者用])

Source

Codeforces Round #209 DIV2 A問題 (500pt)
Problem description

問題概要

縦 $n$ マス,横 $m$ マスのグリッドが与えられる.
各セルは $1$ か $0$ かが書かれている.ただし四隅のセルは全て $0$.
以下の手順を最小で何回繰り返せば,すべてのセルに色を塗ることができるかを求める問題.
 $1$ が書かれているセル $(x_1,\ y_1)$ と,四隅のうちの $1$ つのセル $(x_2,\ y_2)$ を選ぶ.
 その $2$ セルを対角線とする長方形の領域に色を塗る
 つまり,$(x,\ y)$ は $\min(x_1,x_2) \leq x \leq \max(x_1,x_2),\ \min(y_1,y_2) \leq y \leq \max(y_1,y_2)$ であれば色が塗られる.
同じセルに何回色を塗っても良い.
$3 \leq n,m \leq 50$
$1$ が書かれているセルが,少なくても $1$ つある

解法

上下左右の端に $1$ のセルがあれば $2$ 回で全部塗れる.
そうでなければ $4$ 回.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int x, y;
  int mp[51][51];

  int i, j, k;

  scanf("%d%d",&x,&y);
  rep(i,x) rep(j,y) scanf("%d",mp[i]+j);

  k = 0;
  rep(i,x) rep(j,y){
    if(!mp[i][j]) continue;
    if(i==0||j==0||i==x-1||j==y-1) k++;
  }

  if(k) puts("2"); else puts("4");

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2422-db2d8ba9
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。