Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 15:35:01
2016-05-28 15:31:15
2016-05-28 15:00:42
2016-05-28 14:40:55
Task:Ethernet cable
Sender:Team Purkka
Submission time:2016-05-28 15:35:01
Status:READY
Result:WRONG ANSWER

Show test data

Compiler report

input/code.cpp: In function 'void test()':
input/code.cpp:171:8: warning: variable 'vi' set but not used [-Wunused-but-set-variable]
   bool vi[50000];
        ^

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int pos(int x,int y,int z,int w){ // 0<=x<50, 0<=y<50, 0<=z<5, 0<=w<4
  return w*12500+z*2500+y*50+x;
}
int wall(int x,int y,const string &w){
  if(w=="west")return pos(x-1,y-1,0,2);  // 0 = west  = -x
  if(w=="east")return pos(x,y-1,0,3);    // 1 = east  = +x
  if(w=="north")return pos(x-1,y-1,0,2); // 2 = north = -y
  return pos(x-1,y,0,1);                 // 3 = south = +y
}
inline bool walk(char t){
  return t=='D'||t=='.';
}
void test(){
  int w,h;
  cin>>w>>h;
  int sx,sy,ex,ey,sp,ep;
  string ws;
  cin>>sx>>sy>>ws;
  sp=wall(sx,sy,ws);
  cin>>ex>>ey>>ws;
  ep=wall(ex,ey,ws);
  
  char r[2*h+1][2*w+1];
  for(int y=0;y<2*h+1;y++){
    for(int x=0;x<2*w+1;x++)cin>>r[y][x];
  }
  vector<pair<int,int>> co[50000];
  for(int x=0;x<w;x++){
    for(int y=0;y<h;y++){
      char wl=r[2*y+1][2*x],wr=r[2*y+1][2*x+2],wu=r[2*y][2*x+1],wd=r[2*y+2][2*x+1];
      // ----------------- JOHDOT VAAKASUORAAN KATOSSA ---------------
      co[pos(x,y,3,0)].push_back({pos(x,y,3,1),1});
      co[pos(x,y,3,0)].push_back({pos(x,y,3,3),1});
      co[pos(x,y,3,1)].push_back({pos(x,y,3,2),1});
      co[pos(x,y,3,1)].push_back({pos(x,y,3,0),1});
      co[pos(x,y,3,2)].push_back({pos(x,y,3,3),1});
      co[pos(x,y,3,2)].push_back({pos(x,y,3,1),1});
      co[pos(x,y,3,3)].push_back({pos(x,y,3,0),1});
      co[pos(x,y,3,3)].push_back({pos(x,y,3,2),1});
      // ---------------- JOHDOT EI-SEINÄRAJOJEN YLI ------------------
      for(int z=0;z<=3;z++){
	if(x>0&&wl=='.'){ // ei seinää vasemmalla ja ei vasen reuna
	  co[pos(x,y,z,0)].push_back({pos(x-1,y,z,1),0});
	  co[pos(x,y,z,3)].push_back({pos(x-1,y,z,2),0});
	}
	if(x<w-1&&wr=='.'){ // ei seinää oikealla ja ei oikea reuna
	  co[pos(x,y,z,1)].push_back({pos(x+1,y,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x+1,y,z,3),0});
	}
	if(y>0&&wu=='.'){ // ei seinää ylhäällä ja ei yläreuna
	  co[pos(x,y,z,0)].push_back({pos(x,y-1,z,3),0});
	  co[pos(x,y,z,1)].push_back({pos(x,y-1,z,2),0});
	}
	if(y<h-1&&wd=='.'){ // ei seinää alhaalla ja ei alareuna
	  co[pos(x,y,z,3)].push_back({pos(x,y+1,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x,y+1,z,1),0});
	}
	// ---------------- JOHDOT KULMIEN YMPÄRI -----------------
	if(x>0&&y>0){
	  if((wu=='.'&&r[2*y-1][2*x]=='.')||(wl=='.'&&r[2*y][2*x-1]=='.')){
	    co[pos(x,y,z,0)].push_back({pos(x-1,y-1,z,2),0});
	    co[pos(x-1,y-1,z,2)].push_back({pos(x,y,z,0),0});
	  }
	}
	if(x<w-1&&y>0){
	  if((wu=='.'&&r[2*y-1][2*x+2]=='.')||(wr=='.'&&r[2*y][2*x+3]=='.')){
	    co[pos(x,y,z,1)].push_back({pos(x+1,y-1,z,3),0});
	    co[pos(x+1,y-1,z,3)].push_back({pos(x,y,z,1),0});
	  }
	}
	if(x<w-1&&y<h-1){
	  if((wd=='.'&&r[2*y+3][2*x+2]=='.')||(wr=='.'&&r[2*y+2][2*x+3]=='.')){
	    co[pos(x,y,z,2)].push_back({pos(x+1,y+1,z,0),0});
	    co[pos(x+1,y+1,z,0)].push_back({pos(x,y,z,2),0});
	  }
	}
	if(x>0&&y<h-1){
	  if((wd=='.'&&r[2*y+3][2*x]=='.')||(wl=='.'&&r[2*y+2][2*x-1]=='.')){
	    co[pos(x,y,z,3)].push_back({pos(x-1,y+1,z,1),0});
	    co[pos(x-1,y+1,z,1)].push_back({pos(x,y,z,3),0});
	  }
	}
      }
      for(int z=0;z<=2;z++){
	// ------------- JOHDOT OVISTA ---------------
	if(x>0&&wl=='D'){ // ovi vasemmalla ja ei vasen reuna
	  co[pos(x,y,z,0)].push_back({pos(x-1,y,z,1),0});
	  co[pos(x,y,z,3)].push_back({pos(x-1,y,z,2),0});
	}
	if(x<w-1&&wr=='D'){ // ovi oikealla ja ei oikea reuna
	  co[pos(x,y,z,1)].push_back({pos(x+1,y,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x+1,y,z,3),0});
	}
	if(y>0&&wu=='D'){ // ovi ylhäällä ja ei yläreuna
	  co[pos(x,y,z,0)].push_back({pos(x,y-1,z,3),0});
	  co[pos(x,y,z,1)].push_back({pos(x,y-1,z,2),0});
	}
	if(y<h-1&&wd=='D'){ // ovi alhaalla ja ei alareuna
	  co[pos(x,y,z,3)].push_back({pos(x,y+1,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x,y+1,z,1),0});
	}
	// ---------------- JOHDOT KULMIEN YMPÄRI OVISTA -----------------
	if(x>0&&y>0){
	  if((walk(wu)&&walk(r[2*y-1][2*x]))||(walk(wl)&&walk(r[2*y][2*x-1]))){
	    co[pos(x,y,z,0)].push_back({pos(x-1,y-1,z,2),0});
	    co[pos(x-1,y-1,z,2)].push_back({pos(x,y,z,0),0});
	  }
	}
	if(x<w-1&&y>0){
	  if((walk(wu)&&walk(r[2*y-1][2*x+2]))||(walk(wr)&&walk(r[2*y][2*x+3]))){
	    co[pos(x,y,z,1)].push_back({pos(x+1,y-1,z,3),0});
	    co[pos(x+1,y-1,z,3)].push_back({pos(x,y,z,1),0});
	  }
	}
	if(x<w-1&&y<h-1){
	  if((walk(wd)&&walk(r[2*y+3][2*x+2]))||(walk(wr)&&walk(r[2*y+2][2*x+3]))){
	    co[pos(x,y,z,2)].push_back({pos(x+1,y+1,z,0),0});
	    co[pos(x+1,y+1,z,0)].push_back({pos(x,y,z,2),0});
	  }
	}
	if(x>0&&y<h-1){
	  if((walk(wd)&&walk(r[2*y+3][2*x]))||(walk(wl)&&walk(r[2*y+2][2*x-1]))){
	    co[pos(x,y,z,3)].push_back({pos(x-1,y+1,z,1),0});
	    co[pos(x-1,y+1,z,1)].push_back({pos(x,y,z,3),0});
	  }
	}
	// ------------ JOHDOT PYSTYSUORAAN ----------------
	if(walk(wl)||walk(wu)){ // seinä tai ovi ylhäällä tai vasemmalla
	  co[pos(x,y,z,0)].push_back({pos(x,y,z+1,0),1});
	  co[pos(x,y,z+1,0)].push_back({pos(x,y,z,0),1});
	}
	if(walk(wr)||walk(wu)){ // seinä tai ovi ylhäällä tai oikealla
	  co[pos(x,y,z,1)].push_back({pos(x,y,z+1,1),1});
	  co[pos(x,y,z+1,1)].push_back({pos(x,y,z,1),1});
	}
	if(walk(wr)||walk(wd)){ // seinä tai ovi alhaalla tai oikealla
	  co[pos(x,y,z,2)].push_back({pos(x,y,z+1,2),1});
	  co[pos(x,y,z+1,2)].push_back({pos(x,y,z,2),1});
	}
	if(walk(wl)||walk(wd)){ // seinä tai ovi alhaalla tai vasemmalla
	  co[pos(x,y,z,3)].push_back({pos(x,y,z+1,3),1});
	  co[pos(x,y,z+1,3)].push_back({pos(x,y,z,3),1});
	}
	// ------------ JOHDOT VAAKASUORAAN SEINILLÄ ----------------
	if(wl=='|'){ // seinä vasemmalla
	  co[pos(x,y,z,0)].push_back({pos(x,y,z,3),1});
	  co[pos(x,y,z,3)].push_back({pos(x,y,z,0),1});
	}
	if(wr=='|'){ // seinä oikealla
	  co[pos(x,y,z,1)].push_back({pos(x,y,z,2),1});
	  co[pos(x,y,z,2)].push_back({pos(x,y,z,1),1});
	}
	if(wu=='-'){ // seinä ylhäällä
	  co[pos(x,y,z,0)].push_back({pos(x,y,z,1),1});
	  co[pos(x,y,z,1)].push_back({pos(x,y,z,0),1});
	}
	if(wd=='-'){ // seinä alhaalla
	  co[pos(x,y,z,3)].push_back({pos(x,y,z,2),1});
	  co[pos(x,y,z,2)].push_back({pos(x,y,z,3),1});
	}
      }
    }
  }
  priority_queue<pair<int,int>> qu;
  int v[50000];
  bool vi[50000];
  for(int i=0;i<50000;i++){
    v[i]=999999999;
    vi[i]=0;
  }
  v[sp]=0;
  qu.push({0,sp});
  int vic=0;
  while(!qu.empty()){
    pair<int,int> pa=qu.top();
    int d = -pa.first;
    int i = pa.second;
    qu.pop();
    //if (vi[i]) continue;
    vi[i] = true;
    vic++;
    //debug(i);
    for (pair<int, int> p : co[i]) {
	int a = p.first;
	int b = p.second;
	if (v[a] > d + b) {
	    v[a] = d + b;
	    qu.push({-v[a], a});
	}
    }
  }
  cout<<v[ep]<<endl;
}






















void debug(int po){
  int w=po/12500;
  int z=po/2500%5;
  int y=po/50%50;
  int x=po%50;
  cout<<x<<","<<y<<" z="<<z<<" corner "<<w<<endl;
}
int main () {
  int t;
  cin>>t;
  for(int _=0;_<t;_++)test();
}