「AOJ231～240」の編集履歴（バックアップ）一覧に戻る
AOJ231～240 - (2011/09/07 (水) 19:47:43) のソース
*0231 Dangerous Bridge
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0231
橋の通行予定表から橋が壊れるほどの重量がかからないかを調べる問題。
解法
わたる順番と橋を渡り終える順番を時系列順に並べて一からシミュレートするだけです。
#include<stdio.h>
#include<queue>
struct move{
int w,type,time;//wは重さ、0がわたり終わり1がわたり始め
bool operator<(const move m)const{
if(time!=m.time) return time>m.time;
return type>m.type;
}
};
void setData(int n){
std::priority_queue<move> qu;
move m;
int last;
for(int i=0;i<n;i++){
scanf("%d %d %d",&m.w,&m.time,&last);
m.type=1;
qu.push(m);
m.type=0;
m.time=last;
qu.push(m);
}
int allW=0;
bool allOK=true;
while(!qu.empty()){
m=qu.top();
qu.pop();
if(m.type==0){
allW-=m.w;
}else{
allW+=m.w;
}
if(allW>150){
allOK=false;
break;
}
}
printf("%s\n",allOK?"OK":"NG");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0235 Sergeant Rian
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0235
島々でライアン軍層を助けるために橋を効率よく爆破する問題。
木構造で結ばれた島々の出発点から初めて、島から島へ橋で渡りながら最短の移動時間で全ての橋を爆破する時間を求める問題です。
解法
まず末端の島は計算に必要ないので切ります。
後は木構造上での最短経路は同じ橋を２度以上通らないという性質を利用して深さ優先探索で計算します。
この問題、たった１か所のポカミスに気付かず短時間で連続投稿し連続不正解を喰らってしまいました。
コード中の
ans=ans>sum?sum:ans;
moveOKs[now]=true;
return;
の部分のmoveOKs[now]=true;を書き忘れており、発想が正しいはずなのに不正解なので少し熱くなり4連続不正解を喰らってしまいました。
発想が正しいし正解まで後すこしの感じなのでジャッジデータでコードをテストするほうが楽かなという感じでもありましたが、やはり不正解は避けた方がいい。
手元でテストデータを作りしっかりテストすることの大切さを思い知りました。
反省です。
#include<stdio.h>
#include<string.h>
int g[21][21];
int bridgeMoveCount[21][21];//同じ橋を3度は通らないということを利用して全探索
bool moveOKs[21];
int allLand,ans;
int n;
int max=1000000000;
void saiki(int sum,int now,int moveCount){
bool tempMoveOK=false;
if(moveOKs[now]==true){
moveOKs[now]=false;
tempMoveOK=true;
moveCount++;
}
if(moveCount>=allLand){
ans=ans>sum?sum:ans;
moveOKs[now]=true;
return;
}
for(int i=1;i<=n;i++){
if(g[now][i]>0 && bridgeMoveCount[now][i]<2){
bridgeMoveCount[now][i]++;//同じ橋を２度以上通らないということを記録する
bridgeMoveCount[i][now]++;
saiki(sum+g[now][i],i,moveCount);
bridgeMoveCount[now][i]--;
bridgeMoveCount[i][now]--;
}
}
if(tempMoveOK==true){
moveOKs[now]=true;
}
}
void setMap(int n){
int start,goal,time;
memset(g,0,21*21*4);
memset(bridgeMoveCount,0,21*21*4);
memset(moveOKs,true,21);
ans=max;
for(int i=1;i<n;i++){
scanf("%d %d %d",&start,&goal,&time);
g[start][goal]=g[goal][start]=time;
}
int tempSum,p=0,dell[21],temp;
for(int i=2;i<=n;i++){
//計算量を抑えるために末端の島への橋は無視し消去します。橋が一本しかない＝末端の端になります
tempSum=0;
for(int j=1;j<=n;j++){
if(g[i][j]>0){
tempSum++;
}
}
if(tempSum==1){
dell[p]=i;
p++;
}
}
for(int i=0;i<p;i++){
temp=dell[i];
for(int j=1;j<=n;j++){
g[temp][j]=g[j][temp]=0;
}
}
allLand=n-p;
saiki(0,1,0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0) break;
setMap(n);
}
}
----
*0236 Alien Messages
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0236
与えられた盤面で一筆書きが可能かどうか調べる問題。
解法
一筆書きを真面目に深さ優先探索で求めます。
途中で線が盤面を分断してないか、スタートとゴールに到達できない線を引いてないかを調べることで枝がりします。
思考力より真面目な実装が試される問題です。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[10][10];
int checkMap[10][10];
int sx,sy,nowX,nowY;
int w,h,size;
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
bool checkOK;
bool goalRootOK;
int check(int x,int y){
int nx,ny;
int count=0,sum=1;
checkMap[y][x]=-1;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(checkMap[ny][nx]==0){
sum+=check(nx,ny);
if(checkOK==false) return sum;
}
if(checkMap[ny][nx]<1){
count++;
}
}
if(sx==x && sy==y){
goalRootOK=true;
}
if((nowX==x && nowY==y) || (sx==x && sy==y)){
}else{
if(count<2) checkOK=false;
}
return sum;
}
void putMap(){
printf("\n");
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++)printf("%2d",map[i][j]);
printf("\n");
}
printf("\n");
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++)printf("%2d",checkMap[i][j]);
printf("\n");
}
}
bool setCheck(int nX,int nY,int deep){
if(abs(sx-nX)+abs(sy-nY)>size-deep+1) return false;
if(3>deep || deep>=size-2) return true;
memcpy(checkMap,map,400);
checkMap[nY][nX]=checkMap[sy][sx]=0;
nowX=nX;
nowY=nY;
checkOK=true;
goalRootOK=false;
int tt=check(nX,nY);
if(tt==size-deep+1 && goalRootOK==true && checkOK==true){
return true;
}else{
return false;
}
}
bool goalOK;
void saiki(int x,int y,int deep){
if(setCheck(x,y,deep)==false){
return ;
}
if(deep!=size && deep!=0 && sx==x && sy==y){
return;
}
if(deep==size && sx==x && y==sy){
goalOK=true;
return;
}
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(map[ny][nx]==0){
map[ny][nx]=1;
saiki(nx,ny,deep+1);
if(goalOK==true) return;
map[ny][nx]=0;
}
}
}
void setData(){
size=0;
for(int i=0;i<=h+1;i++){
for(int j=0;j<=w+1;j++){
if(i==0 || j==0 || i==h+1 || j==w+1){
map[i][j]=1;
}else{
scanf("%d",&map[i][j]);
if(map[i][j]==0){
sy=i;
sx=j;
size++;
}
}
}
}
goalOK=false;
if(size<4 || size%2==1){
goalOK=false;
}else{
saiki(sx,sy,0);
}
if(goalOK==true){
printf("Yes\n");
}else{
printf("No\n");
}
}
int main(){
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setData();
scanf("%d %d",&w,&h);
}
}
