2017 Karakuri Doll
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017
壁にあたるたびに右か左に移動するパタンをプログラムされた人形が迷路になっている屋敷を抜けてゴールまで辿りつき、プログラムを逆実行してゴールからスタートへ戻れるかを問う問題。
右が左で左が右で混乱した問題。
この問題は行きはよいよい帰りは恐い。
行きは前に通ったのと同じ状態になったら探索を止める幅優先探索で楽勝、中学生でも解けそうな問題。
帰りは、行きを逆回しで行う探索と*帰りの探索をセットで行いセットで探索する必要がありかなり混乱した。
pointはx,y,rが位置と今の人形の向きを表します。
rePoint構造体で帰りの探索とゴールから始める行きの逆回しをpoint２つで記憶します。
スタートやゴールからある地点にある向きで到達するプログラムが複数ある時、途中の人形プログラムがどうであろうと、その人形プログラムはその地点にある特定の向きで到達するプログラムであるという共通点があり、一度一つのプログラムを見つければ他のプログラムは必要ありません。
これを使って探索を枝かりできるわけです、具体的にはmemosを使っています。
後は、逆回し+ゴールからスタートへのルート探索をnextsCalcで探索して幅優先探索に追加していけばいいだけです。
素朴な発想で書いたのでコードサイズも膨らんだし速度も出てませんが素朴なだけに分かりやすくメモリも使わないとコードという利点があります。
#include<stdio.h>
#include<set>
#include<queue>
struct point{
int x,y,r;
bool operator<(const point& p)const{
if(x!=p.x)return x<p.x;
if(y!=p.y)return y<p.y;
if(r!=p.r)return r<p.r;
return false;
}
bool operator!=(const point& p)const{
if(x!=p.x)return x!=p.x;
if(y!=p.y)return y!=p.y;
if(r!=p.r)return r!=p.r;
return false;
}
};
struct rePoint{
point p1,p2;
bool operator<(const rePoint& rp)const{
if(p1!=rp.p1)return p1<rp.p1;
if(p2!=rp.p2)return p2<rp.p2;
return false;
}
};
bool startOK,returnOK;
int sx,sy,gx,gy;
char map[18][70];
int startR;
//char muki[4][6]={"→","↓","←","↑"};
int dxs[]={1,0,-1,0};//右下左上1増えると右回り
int dys[]={0,1,0,-1};
void okCheck(const point& p){
if(p.x==gx&&p.y==gy){
startOK =true;
}
}
void okCheckRe(const rePoint& p){
if(p.p1.x==sx&&p.p1.y==sy&&p.p2.x==sx&&p.p2.y==sy&&startR==p.p2.r){
//printf("\n+++++++<<%d %d>>\n",p.p1.r,p.p2.r);
returnOK=true;
}
}
void nextStopPoint(const point& p,point& next){
next.r=p.r;
for(int i=1;i<100;i++){
int dx=p.x+dxs[p.r]*i;
int dy=p.y+dys[p.r]*i;
if(map[dy][dx]=='#'){
next.x=p.x+dxs[p.r]*(i-1);
next.y=p.y+dys[p.r]*(i-1);
break;
}
}
}
void nextsCalc(const rePoint& nowP,std::set<rePoint>& memo,std::queue<rePoint>& now){
rePoint next=nowP;
nextStopPoint(nowP.p1,next.p1);
int r2=nowP.p2.r;
//printf("\n<0(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
for(int i=0;i<100;i++){
int nowX=nowP.p2.x+dxs[r2]*i;
int nowY=nowP.p2.y+dys[r2]*i;
//printf("(%d %d %c)",nowX,nowY,map[nowY][nowX]);
if(map[nowY][nowX]=='#'){
return;
}
//帰りが右向き
int dx=nowX+dxs[(r2+3)%4];
int dy=nowY+dys[(r2+3)%4];
if(map[dy][dx]=='#'){
next.p2.x=nowX;
next.p2.y=nowY;
next.p2.r=r2;
okCheckRe(next);
next.p2.r=(r2+1)%4;
next.p1.r=(nowP.p1.r+1)%4;
//printf(",<1(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
if(memo.find(next)==memo.end()){
okCheckRe(next);
memo.insert(next);
now.push(next);
}
}
dx=nowX+dxs[(r2+1)%4];
dy=nowY+dys[(r2+1)%4];
if(map[dy][dx]=='#'){
next.p2.x=nowX;
next.p2.y=nowY;
next.p2.r=r2;
okCheckRe(next);
next.p2.r=(r2+3)%4;
next.p1.r=(nowP.p1.r+3)%4;
//printf("<2(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
if(memo.find(next)==memo.end()){
okCheckRe(next);
memo.insert(next);
now.push(next);
}
}
}
}
void reCalc(rePoint nowP,int r2){
std::set<rePoint> memos;
std::queue<rePoint> nows;
for(int i=0;i<4;i++){
nowP.p2.r=i;
if(i==(r2+2)%4)continue;
nows.push(nowP);
}
int count=1;
while(!nows.empty()){
nowP=nows.front();
//if(count%20==0)scanf("%d",&count);
//count++;
nows.pop();
if(returnOK==true)break;
nextsCalc(nowP,memos,nows);
}
}
bool calc(){
startOK=false;
returnOK=false;
int h,w,r1,r2;
char c;
scanf("%d %d",&w,&h);
if(w==0&&h==0)return false;
for(int i=0;i<h;i++){
scanf("%s",map[i]);
}
for(int i=1;i<h-1;i++){
for(int j=1;j<w-1;j++){
c=map[i][j];
if(c=='K'){
sx=j;
sy=i;
for(int k=0;k<4;k++){
int dx=j+dxs[k];
int dy=i+dys[k];
if(map[dy][dx]!='#')r1=k;
}
}else if(c=='M'){
gx=j;
gy=i;
for(int k=0;k<4;k++){
int dx=j+dxs[k];
int dy=i+dys[k];
if(map[dy][dx]!='#')r2=k;
}
}
}
}
std::set<point> memos;
std::queue<point> nows;
point next,temp;
point p;
p.x=sx;
p.y=sy;
p.r=r1;
nextStopPoint(p,next);
memos.insert(next);
nows.push(next);
while(!nows.empty()){
p=nows.front();
okCheck(p);
//printf("(%d %d %s)",p.x,p.y,muki[p.r]);
if(startOK==true) break;
temp=nows.front();
nows.pop();
temp.r=(p.r+1)%4;
nextStopPoint(temp,next);
if(memos.find(next)==memos.end()){
memos.insert(next);
nows.push(next);
}
temp.r=(p.r+3)%4;
nextStopPoint(temp,next);
if(memos.find(next)==memos.end()){
memos.insert(next);
nows.push(next);
}
}
if(startOK==true){
rePoint rp;
rp.p1.x=gx;
rp.p1.y=gy;
rp.p2.x=gx;
rp.p2.y=gy;
rp.p1.r=r2;
startR=(r1+2)%4;
//printf("(r1=%d startR=%d)\n",r1,startR);
reCalc(rp,r2);
}
if(returnOK==true){
printf("He can accomplish his mission.\n");
}else if(startOK==true){
printf("He cannot return to the kitchen.\n");
}else{
printf("He cannot bring tea to his master.\n");
}
return true;
}
int main(){
while(calc()){
}
}
2019 Princess's Marriage
#include<stdio.h>
#include<vector>
#include <algorithm>
struct load{
int len,p;
bool operator<(const load& l)const{
return p>l.p;
}
};
int n,m;
void calc(){
std::vector<load> loads;
load l;
for(int i=0;i<n;i++){
scanf("%d %d",&l.len,&l.p);
loads.push_back(l);
}
std::sort(loads.begin(),loads.end());
bool last=false;
int ans=0;
for(int i=0;i<n;i++){
m-=loads[i].len;
if(m<0&&last==false){
last=true;
ans=-m*loads[i].p;
}else if(last==true){
ans+=loads[i].p*loads[i].len;
}
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF){
if(n==0&&m==0) break;
calc();
}
}
