Submission #1173286

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<bitset>
#include<cstdlib>
#include<random>

using namespace std;

typedef bitset<900> BS;
constexpr int H=30,W=30,K=450,T=10000;
int A[K],B[K],C[K],D[K];

mt19937 engine;

int main(){
  int h,w,kk,t;
  cin>>h>>w>>kk>>t;
  for(int i=0;i<K;i++){
    cin>>A[i]>>B[i]>>C[i]>>D[i];
    A[i]--;
    B[i]--;
    C[i]--;
    D[i]--;
  }
  vector<string> ans;
  double score=0;
  for(;;){
    int a[K],b[K];
    copy(begin(A),end(A),begin(a));
    copy(begin(B),end(B),begin(b));
    BS cars;
    for(int i=0;i<K;i++){
      cars[a[i]*W+b[i]]=true;
    }
    vector<string> cans;
    for(int i=0;;i++){
      double cpd=20;
      for(int j=0;j<K;j++){
	cpd+=abs(a[j]-C[j])+abs(b[j]-D[j]);
      }
      double cpt=10+i*0.01;
      double cscore=10000000./(cpd*cpt);
      if(cscore>score){
	ans=cans;
	score=cscore;
      }

      if(i==T)break;
      
      BS ncars,cncars=cars;
      int oa[K],ob[K];
      copy(begin(a),end(a),begin(oa));
      copy(begin(b),end(b),begin(ob));
      string moves;
      for(int k=0;k<K;k++){
	vector<int> cands;
	const static int dy[]={-1,0,1,0,0};
	const static int dx[]={0,1,0,-1,0};
	for(int l=0;l<4;l++){
	  int ny=oa[k]+dy[l];
	  int nx=ob[k]+dx[l];
	  if(0<=ny&&ny<H&&0<=nx&&nx<W&&!cncars[ny*W+nx]){
	    if(abs(ny-C[k])+abs(nx-D[k])<abs(oa[k]-C[k])+abs(ob[k]-D[k])){
	      cands.push_back(l);
	    }
	  }
	}
	int m=cands.empty()?4:cands[uniform_int_distribution<>(0,cands.size()-1)(engine)];
	moves+="URDL-"[m];
	a[k]+=dy[m];
	b[k]+=dx[m];
	int y=a[k],x=b[k];
	ncars[y*W+x]=true;
	cncars[y*W+x]=true;
      }
      cars=ncars;
      cans.push_back(moves);
    }
    break;
  }

  cout<<ans.size()<<endl;
  for(auto e:ans){
    cout<<e<<endl;
  }
}

Submission Info

Judge Result