chigichan24のお気持ち表明

おきもちを表明している

テスト1日目+誰か教えてください

一つ前の記事のちょっとした続き.


例のICT Summer Contest 2014 Day1(Hard)の問題の最後の問題を解いてみた.

I - Family's Kyoto-Custom Experience Tour(hard edition)

  • 他の人の解法を見てみたら、全く違ったのでこわい><
  • 割と強めの枝狩り全探索で通りました.
  • 初めてです.こういう体験.
  • ひょっとして嘘解法?
  • 本来の解法は逆元とか使うようだ(人のコードを見た限りでは)
  • と見せかけて、実はこれが想定解?なのかは不明なので,誰か教えてください!

コード

class data{
    public:
    int ay,ax;
    int by,bx;
    int cnt;
    data(){};
    data(int a,int b,int c,int d,int _cnt){
	ay = a;
	ax = b;
	by = c;
	bx = d;
	cnt=_cnt;
    }
};
int main(){
    int h,w,y,x;
    cin >> h >> w >> y >> x;
    h--;w--;
    queue < data > Q;
    Q.push(data(0,0,h,w,0));
    int ans=0;
    int path = max(abs(h-y)+abs(w-x),x+y);
    while(!Q.empty()){
	data d = Q.front();Q.pop();
	if(path == d.cnt && d.ay == y && d.ax == x && d.by == y && d.bx == x){
	   ans++;
	   continue;
	}	   
	if(path <= d.cnt)continue;
	rep(i,2){
	    int ny = d.ay+dy[i];
	    int nx = d.ax+dx[i];
	    if(ny > y || nx > x)continue;
	    Q.push(data(ny,nx,d.by,d.bx,d.cnt+1));
	}
	reps(i,2,4){
	    int ny = d.by+dy[i];
	    int nx = d.bx+dx[i];
	    if(ny < y || nx < x)continue;
	    Q.push(data(d.ay,d.ax,ny,nx,d.cnt+1));
	}
	rep(i,2){
	    int ny = d.ay+dy[i];
	    int nx = d.ax+dx[i];
	    if(ny > y || nx > x)continue;
	    reps(j,2,4){
                int nny = d.by+dy[j];
	        int nnx = d.bx+dx[j];
		if(nny < y || nnx < nx)continue;
		Q.push(data(ny,nx,nny,nnx,d.cnt+1));
	    }
	}
    }
    printf("%d\n%d\n",path,ans);
    return 0;
}