競プロはじめました

競プロ初心者のブログ

AOJ0558

AOJ0558

チーズ | Aizu Online Judge

幅優先探索の練習第二弾です。 こちらは方針がすぐにたち、2,30分くらいで書きました。 が、枝刈りしてなかったので大きいデータに殺されましたチーン

すでに通った座標をキューに入れないように書いたのですが、条件式のxとyの逆に書いてたことに気付かないで二三十分苦戦してました。

発見

  • queueはclear()がない。だから、空のqueueとswapさせるとよい

解答時間は50分でした。

以下、コードです

#include <stdio.h>
#include <queue>

using namespace std;

typedef pair<int,int> P;

int h, w, n;
char field[1000][1001];
queue<P> qu;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int d[1000][1000];


void init(){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      d[i][j] = -1;
    }
  }
  queue<P> empty;
  swap(qu,empty);
}

int solve(){
  int hp = 1;
  int cnt;
  init();
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(field[i][j] == 'S'){
        qu.push(P(i,j));
        d[i][j] = 0;
      }
    }
  }
  while(qu.size()){
    P p = qu.front();
    qu.pop();
    int y = p.first;
    int x = p.second;
    if(hp == n + 1)
      return d[y][x];
    if(hp == field[y][x] - '0'){
      hp++;
      cnt = d[y][x];
      init();
      d[y][x] = cnt;
    }
    for(int i = 0; i < 4; i++){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(ny >= 0 && ny < h && nx >= 0 && nx < w && field[ny][nx] != 'X' && d[ny][nx] == -1){
        d[ny][nx] = d[y][x] + 1;
        qu.push(P(ny,nx));
      }
    }
  }
  return 0;
}

int main(){
  scanf("%d %d %d", &h, &w, &n);
  for(int i = 0; i < h; i++){
    scanf("%s", field[i]);
  }
  printf("%d\n", solve() - 1);
  return 0;
}

AOJ0121

AOJ0121

7 パズル | Aizu Online Judge

幅優先探索の練習です。

入出力のところで戸惑いました。 iostreamを使わなきゃいけないんですかね。。。?

今回は方針が全然立ちませんでした。 最初、それぞれのデータセットに対して毎回計算させてました。 最初に計算して、与えられたセットに対して値を返すmapを作成すればいいんですね。。。

拘束条件も正確ではなくて闇を見ました。 問題をわかりやすくするために文字列として扱ったのはいいものの、問題の状況を完全に見落としてました。

いろいろ苦難して解答時間は三時間です

以下、コードです

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

string data;
char goal[9] = "01234567";
queue<string> qu;
map<string,int> mp;
int d[4] = {-4,-1,1,4};
int pos;
int ans[1000];
char tmp;


void solve(){
  mp[goal] = 0;
  qu.push(goal);
  string pre_data;
  while(qu.size()){
    data = qu.front();
    pre_data = data;
    qu.pop();
    pos = data.find('0');
    for(int i = 0; i < 4; i++){
      if(pos + d[i] >= 0 && pos + d[i] < 8 && !(pos == 3 && d[i] == 1) && !(pos == 4 && d[i] == -1)){
        data = pre_data;
        swap(data[pos],data[pos+d[i]]);
        if(mp.find(data) == mp.end()){
          mp[data] = mp[pre_data] + 1;
          qu.push(data);
        }
      }
    }
  }
}

int main(){
  int n = 0;
  size_t c;
  solve();
  while(getline(cin, data)){
    while((c = data.find_first_of(" ")) != string::npos){
      data.erase(c,1);
    }
    ans[n++] = mp[data];
  }
  for(int i = 0; i < n; i++)
    printf("%d\n", ans[i]);
}

AOJ0033

AOJ0033

玉 | Aizu Online Judge

深さ優先探索の練習第二弾 今回は割とすぐ解法が思いつきました。 解答時間は25分でした。

solveでどこでreturn falseすればいいのか迷いました。

以下コードです。

#include <stdio.h>

int n;
int data[10];
int ans[100];

bool solve(int i, int l, int r){
  if(i==10)
    return true;
  if(data[i] > l)
    return solve(i+1,data[i],r);
  if(data[i] > r)
    return solve(i+1,l,data[i]);
  return false;
}
int main(){
  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 10; j++){
      scanf("%d", &data[j]);
      if(solve(0,0,0)){
        ans[i] = 1;
      }else{
        ans[i] = 0;
      }
    }
  }
  for(int i = 0; i < n; i++){
    if(ans[i])
      printf("YES\n");
    else
      printf("NO\n");
  }
}

AOJ0118

AOJ0118

財産分配 | Aizu Online Judge

深さ優先探索の練習として解きました。 うる覚え深さ優先探索だったので解答時間は1時間でした。

最初、dfsの中に一緒にsumを計算させようとして、うまくいきませんでした

以下、コードです

#include <stdio.h>

int h, w;
char map[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ans[20];
void dfs(int i, int j, char tree){
  map[i][j] = '.';
  int x, y;
  for(int l = 0; l < 4; l++){
    x = j + dx[l];
    y = i + dy[l];
    if(y < h && y >= 0 && x < w &&  x >= 0 && map[y][x] == tree){
      dfs(y,x,tree);
    }
  }
  return;
}

int solve(){
  int sum = 0;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(map[i][j] != '.'){
        dfs(i, j, map[i][j]);
        sum++;
      }
    }
  }
  return sum;
}

int main(){
  int n = 0;
  while(true){
    scanf("%d %d", &h, &w);
    if(h == 0 && w == 0)
      break;
    for(int i = 0; i< h; i++){
      scanf("%s",map[i]);
    }
    ans[n++] = solve();
  }
  for(int i = 0; i < n; i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}