beet's soil

競プロのことなど

SRM 706 Div1

仮眠して出た

【Easy- MovingCandies】

概要

.と#からなるグリッドが与えられる。
左上から#だけを通って右下まで行けるようにするために、
動かさなければいけない#の数の最小値を求める。
(到達できない場合は-1。)

解法

dp[y][x][#を通った数]:=.を通った数の最小値 でbfsした。
01bfsだからdequeue使うべきだったんだろうけどそこまで考えが回らなかった。
最悪ケースでも状態数が20*20*400しかないので回るのでよし。

ソースコード
  int m[20][20][400];
  struct st{
    int y,x,a,b;
    st(){}
    st(int y,int x,int a,int b):y(y),x(x),a(a),b(b){}
  };
  bool out(int h,int w,int y,int x){
    return y<0||h<=y||x<0||w<=x;
  }
  int minMoved(vector <string> t) {
    for(int i=0;i<20;i++)
      for(int j=0;j<20;j++)
	for(int k=0;k<400;k++)
	  m[i][j][k]=1000;
    int h=t.size(),w=t[0].size(),c=0;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	if(t[i][j]=='#') c++;
    if(c<w+h-1) return -1;
    typedef pair<int,int> P;
    int ax[]={1,-1,0,0};
    int ay[]={0,0,1,-1};
    if(t[0][0]=='#'&&t[h-1][w-1]=='#'){
      bool u[20][20]={};
      queue<P> q;
      q.push(P(0,0));
      while(!q.empty()){
	P p=q.front();q.pop();
	int y=p.first,x=p.second;
	if(u[y][x]) continue;
	u[y][x]=1;
	for(int k=0;k<4;k++){
	  int by=y+ay[k],bx=x+ax[k];
	  if(out(h,w,by,bx)) continue;
	  if(t[by][bx]=='#') q.push(P(by,bx));
	}
      }
      if(u[h-1][w-1]) return 0;
    }
    int res=w+h-1;
    queue<st> q;
    q.push(st(0,0,t[0][0]=='#',t[0][0]!='#'));
    while(!q.empty()){
      st s=q.front();q.pop();
      if(s.a>c) continue;
      if(m[s.y][s.x][s.a]<=s.b) continue;
      m[s.y][s.x][s.a]=s.b;
      for(int k=0;k<4;k++){
	int by=s.y+ay[k],bx=s.x+ax[k];
	if(out(h,w,by,bx)) continue;
	if(t[by][bx]=='#'&&s.b<m[by][bx][s.a+1]) q.push(st(by,bx,s.a+1,s.b));
	if(t[by][bx]=='.'&&s.b+1<m[by][bx][s.a]) q.push(st(by,bx,s.a,s.b+1));
      }
    }
    for(int i=0;i<400;i++)
      if(i+m[h-1][w-1][i]<=c) res=min(res,m[h-1][w-1][i]);
    return res;
  }

【全体】

162nd 1204->1319 (+115)
念願のdiv1でAC!!ABC効果だろうか。
Easyをコンスタントに通せるようになりたい。