JOI本選対策です。

予選ギリギリ通過勢なんで、基礎的なアルゴリズムから

POJ1979 [Red and Black]

問題文はこちら

  • やるだけ
  • 深さ優先探索
  • はい。
  • Cの理解が浅すぎてscanfどーやるんだっけとかなった。
#include <iostream>
#include <cstdio>

using namespace std;

char pou[23][23];

int w=0,h=0;

int ans = 0;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

void dfs(int y,int x){

  pou[y][x] = #;

  for(int i = 0;i < 4;i++){
    int xx = x+dx[i];
    int yy = y+dy[i];
    if(xx < w && yy < h && xx >= 0 && yy >= 0 && pou[yy][xx] == .){
      ans++;
      dfs(yy,xx);
    }
  }
}





int main(){

  while(1){

    ans = 1;

    scanf("%d %d",&w,&h);

    if(w == 0) break;

    for(int i = 0;i < h;i++){
      scanf("%s",pou[i]);
  }

    for(int i = 0;i < h;i++){
      for(int j = 0;j < w;j++){
	if(pou[i][j] == @){
	  dfs(i,j);
	  goto out;
	}
      }
    }
  out:
    ;
    printf("%d
",ans);

  }

  return 0;
}
AOJ0118 [Property Distribution]

問題文はこちら


  • やるだけ
  • りんごかきみかん
  • PCKの問題ぢゃん
#include <cstdio>

using namespace std;

char pou[103][103];

int h=0,w=0;

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

int ans = 0;

void dfs(int y,int x,char tmp){
  pou[y][x] = d;

  for(int i = 0;i < 4;i++){
    int xx = x+dx[i];
    int yy = y+dy[i];
    if(xx >= 0 && yy >= 0 && xx < w && yy < h && pou[yy][xx] == tmp){
      dfs(yy,xx,tmp);
    }
  }
}





int main(){

  while(1){

    ans = 0;

    scanf("%d %d",&h,&w);

    if(h == 0) break;

    for(int i = 0;i < h;i++){
      scanf("%s",pou[i]);
    }

    for(int i = 0;i < h;i++){
      for(int j = 0;j < w;j++){
	if(pou[i][j] != d){
	  ans++;
	  dfs(i,j,pou[i][j]);
	}
      }
    }

    printf("%d
",ans);

  }
}
AOJ0033 [Ball]

問題文はこちら

  • 典型的な全探索です。
  • やるだけとしか言えない...
  • こちらもPCKの問題。(PCKでたいです。
#include <cstdio>
#include <iostream>

using namespace std;

int pou[12] = {0};


int dfs(int nau,int b,int c){
  if(nau == 11) return 1;
  if(pou[nau-1] > b){
    if( dfs(nau+1,pou[nau-1],c) == 1){
      return 1;
    }
  }

  if(pou[nau-1] > c){
    if( dfs(nau+1,b,pou[nau-1])==1){
      return 1;
    }
  }

  return 0;
}



int main(){

  int n=0;

  scanf("%d",&n);

  for(int i = 0;i < n;i++){

    for(int j = 0;j < 10;j++){
      scanf("%d",&pou[j]);
    }

    if(dfs(1,0,0) == 1){
      printf("YES
");
    }else{
      puts("NO");
    }
  }
  return 0;
}

なんか気分悪くなってきたからやめよう