スポンサーサイト

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

AOJ 0118 Property Distribution

蟻本に載ってたPOJ2386とだいたい同じ。
同じグループを消してく。

int H,W;
char map[100][100];

void grouping(int h,int w,char f);

int main(){
while(1){
cin >> H >> W;
if(H==0&&W==0)break;

for(int i=0;i for(int j=0;j cin >> map[i][j];
}
}
int x=0;
for(int i=0;i for(int j=0;j if(map[i][j]!='.'){
x++;
grouping(i,j,map[i][j]);
}
}
}
cout << x << endl;
}
}

void grouping(int h,int w,char f){
map[h][w] = '.';
if(h-1>=0&&map[h-1][w]==f){
grouping(h-1,w,f);
}
if(h+1 grouping(h+1,w,f);
}
if(w-1>=0&&map[h][w-1]==f){
grouping(h,w-1,f);
}
if(w+1 grouping(h,w+1,f);
}
}


スポンサーサイト

AOJ 0525 Osenbei

0の個数を最大にするとき、どの行をひっくり返すか決めると
ひっくり返すべき列とそれで得られる0の個数が一意的に決まる。
Rが十分に小さいので行のひっくり返し方を全通り試し
そのひっくり返し方に対応する0の個数の最大を出力する。
行のひっくり返し方を再帰で書くとこんな感じ

int senbei[10][10000];
int r,c;
int rowFlag[10];
int Max;

void countSum(){
int sum=0;
for(int i=0;i int colSum = 0;
for(int j=0;j if(senbei[j][i]==!rowFlag[j]){
colSum++;
}
}
sum += max(colSum,r-colSum);
}
if(Max Max = sum;
}
}

void setFlag(int pos){
if(pos==r){
countSum();
return;
}
rowFlag[pos] = 1;
setFlag(pos+1);

rowFlag[pos] = 0;
setFlag(pos+1);
}

int main(){
while(1){
cin >> r >> c;
if(r==0&&c==0) return 0;
for(int i=0;i for(int j=0;j cin >> senbei[i][j];
}
}
Max = 0;
setFlag(0);
cout << Max << endl;
}
}




再帰を使わないで蟻本っぽく解くならこんな感じ?
通ったから一応あってると思う。


int senbei[10][10000];
int r,c;
int rowFlag[10];
int Max;

int countSum(){
int sum=0;
for(int i=0;i int colSum = 0;
for(int j=0;j if(senbei[j][i]==!rowFlag[j]){
colSum++;
}
}
sum += max(colSum,r-colSum);
}
return sum;
}

int main(){
while(1){
cin >> r >> c;
if(r==0&&c==0) return 0;
for(int i=0;i for(int j=0;j cin >> senbei[i][j];
}
}
Max = 0;
for(int i=0;i<1< for(int j=0;j rowFlag[j] = i >> j & 1;
}
int sum = countSum();
if(Max Max = sum;
}
}
cout << Max << endl;
}
}


AOJ 0121 Seven Puzzle

幅優先探索の問題
まず考えたのは、初期状態から0をどんどん移動させて行く方法。
パズルの状態はstringで表現している。
mapで状態とそこまでの最短距離を対応させ、
mapに存在するかどうかでたどり着いたことがあるかを確認。
ただ、これだとTLEをくらう。

//TLEをくらうコード

void swap(char *a,char *b){
char temp = *a;
*a = *b;
*b = temp;
}

int main(){
int dx[] = {+1,-1,+4,-4};
while(1){
string input = "";
char temp;
for(int i=0;i<8;i++){
if(cin >> temp){
input.push_back(temp);
}else{
return 0;
}
}

queue que;
map d;
que.push(input);
d[input] = 0;

while(que.size()){
string q = que.front(); que.pop();
if(q=="01234567"){
break;
}
int x = q.find("0");
for(int i=0;i<4;i++){
int next = x + dx[i];
if( next>=0 && next<=7 && !(x==3&&next==4) && !(x==4&&next==3) ){
string nextq = q;
swap(&nextq[x],&nextq[next]);
if(d.find(nextq)==d.end()){
que.push(nextq);
d[nextq] = d[q] + 1;
}
}
}
}
cout << d["01234567"] << endl;
}
}



inputは1000個まで与えられるので、
毎回一から探索していっているのでは無駄が多い。
そもそも、ありえる状態は8!通りしかないから
そろった状態からたどりつけるすべての状態への最短距離を計算しておき
inputに対応した最短距離を出力するほうがいい。
同じようにmapを使って状態と最短距離を対応させる。


//通ったコード

void swap(char *a,char *b){
char temp = *a;
*a = *b;
*b = temp;
}

int main(){
int dx[] = {+1,-1,+4,-4};

string start = "01234567";

queue que;
map d;
que.push(start);
d[start] = 0;

while(que.size()){
string q = que.front(); que.pop();
int x = q.find("0");
for(int i=0;i<4;i++){
int next = x + dx[i];
if( next>=0 && next<=7 && !(x==3&&next==4) && !(x==4&&next==3) ){
string nextq = q;
swap(&nextq[x],&nextq[next]);
if(d.find(nextq)==d.end()){
que.push(nextq);
d[nextq] = d[q] + 1;
}
}
}
}

while(1){
string input = "";
char temp;
for(int i=0;i<8;i++){
if(cin >> temp){
input.push_back(temp);
}else{
return 0;
}
}
cout << d[input] << endl;
}

}


AOJ 0033 Ball

初めて書いた(?)深さ優先探索
条件がかなり緩いので全探索可能

int n;
int ba[10];

bool all(int,int,int);

int main(){
cin >> n;
for(int i=0;i for(int j=0;j<10;j++){
cin >> ba[j];
}
if(all(0,0,0)){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
}

bool all(int end,int l,int r){
if(end==10){
return true;
}
if(ba[end]>l){
return all(end+1,ba[end],r);
}
if(ba[end]>r){
return all(end+1,l,ba[end]);
}
return false;
}


蟻本やってます

7月にあるICPC国内予選に向けて蟻本を解いています。
せっかく書いたソースコードをそのままにしておくのももったいないので
ここにガシガシ載っけていこうかなと思います。

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