yukicoder No.85 - TVザッピング(1)

Source

ニコニコミュニティ
問題文

問題概要

$N$ 行 $M$ 列のマス目が合って,row-major orderで番号が付いている.
番号 $C$ のマスから初めて,上下左右に移動して,全部のマスを $1$ 回だけ通って $C$ のマスに帰ってこれるかどうかを判定する問題.
(番号 $C$ のマスだけは最初と最後の $2$ 回通る)

解法

$N=1$ または $M=1$ の場合は,$NM=2$ の時のみ可能.
$N,M \geq 2$ の場合は,$N$ も $M$ も奇数の時のみ不可能.
これが不可能なのは,市松模様に塗って,それぞれの色のマスの数が $2$ 違うので無理.
それ以外は可能で,実際に,ジグザクと動けば達成する方法のパターンを思いつける.
閉路なので,どこから始めても関係ないので,$C$ は使用しない.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

#define MD 1000000007

int main(){
  int N, M, C;
  reader(&N,&M,&C);
  if(N==1 || M==1){
    if(N*M==2) writerLn("YES"); else writerLn("NO");
    return 0;
  }
  writerLn(N%2 && M%2 ? "NO":"YES");

  return 0;
}

Current time: 2024年03月29日04時27分05秒
Last modified: 2014年12月05日00時24分49秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: