JOI本選対策1日目

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\n",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\n",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\n");
    }else{
      puts("NO");
    }
  }
  return 0;
}

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