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:44:53
2016-05-28 14:53:26
2016-05-28 14:45:18
2016-05-28 14:33:28
2016-05-28 14:25:50
Task:Ethernet cable
Sender:Game of Nolife
Submission time:2016-05-28 15:44:53
Status:READY
Result:WRONG ANSWER

Show test data

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

string ss[200];

char gett(int y, int x){
	return ss[y*2][x*2+1];
}
char getb(int y, int x){
	return ss[y*2+2][x*2+1];
}
char getl(int y, int x){
	return ss[y*2+1][x*2];
}
char getr(int y, int x){
	return ss[y*2+1][x*2+2];
}

int dist[155][155][4][4];
int u[155][155][4][4];

pair<pair<int, int>, int> toC(int y, int x, string d){
	if (d=="east"){
		return {{y, x}, 0};
	}
	else if (d=="west"){
		return {{y, x-1}, 1};
	}
	else if (d=="south"){
		return {{y, x}, 0};
	}
	else if (d=="north"){
		return {{y-1, x}, 2};
	}
	else{
		assert(0);
	}
}
int w,he;
void go(deque<pair<pair<int, int>, pair<int, int> > >&bfs, int d, int y, int x, int h, int di, int a){
	if (y<0||y>he+4) return;
	if (x<0||x>w+4) return;
	if (u[y][x][h][di]==0){
		dist[y][x][h][di]=d+a;
		u[y][x][h][di]=1;
		if (a==0) bfs.push_front({{y, x}, {h, di}});
		else bfs.push_back({{y, x}, {h, di}});
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		cin>>w>>he;
		int sx,sy,ex,ey;
		string sd,ed;
		cin>>sx>>sy>>sd;
		cin>>ex>>ey>>ed;
		sx++;
		sy++;
		ex++;
		ey++;
		ss[0]="";
		ss[1]="";
		ss[2*he+3]="";
		ss[2*he+4]="";
		for (int i=0;i<2*w+5;i++){
			ss[0]+='.';
			ss[1]+='.';
			ss[2*he+4]+='.';
			ss[2*he+3]+='.';
		}
		for (int i=2;i<=2*he+2;i++){
			cin>>ss[i];
			ss[i]=".."+ss[i];
			ss[i]+="..";
		}
		for (int i=0;i<=2*he+4;i++){
			//cout<<ss[i]<<endl;
		}
		memset(dist, 0, sizeof(dist));
		memset(u, 0, sizeof(u));
		deque<pair<pair<int, int>, pair<int, int> >> bfs;
		auto ca=toC(sy, sx, sd);
		auto cl=toC(ey, ex, ed);
		//cout<<ca.F.F<<" "<<ca.F.S<<endl;
		go(bfs, 0, ca.F.F, ca.F.S, 0, ca.S, 0);
		while (!bfs.empty()){
			auto t=bfs.front();
			bfs.pop_front();
			int y=t.F.F;
			int x=t.F.S;
			int h=t.S.F;
			int di=t.S.S;
			int d=dist[y][x][h][di];
			int onw=0;
			if (di==0&&(gett(y, x)!='.'||getl(y, x)!='.')) onw=1;
			if (di==1&&(gett(y, x)!='.'||getr(y, x)!='.')) onw=1;
			if (di==2&&(getb(y, x)!='.'||getl(y, x)!='.')) onw=1;
			if (di==3&&(getb(y, x)!='.'||getr(y, x)!='.')) onw=1;
			
			//cout<<y<<" "<<x<<" "<<h<<" "<<di<<" "<<onw<<endl;
			//cout<<d<<endl;
			
			//seinaa ylos alas
			if (h<3&&onw) {
				go(bfs, d, y, x, h+1, di, 1);
			}
			if (h>0&&onw) go(bfs, d, y, x, h-1, di, 1);
			
			//toiseen tileen
			if (di==0){
				if (gett(y, x)=='.') go(bfs, d, y-1, x, h, 2, 0);
				if (getl(y, x)=='.') go(bfs, d, y, x-1, h, 1, 0);
			}
			if (di==1){
				if (gett(y, x)=='.') go(bfs, d, y-1, x, h, 3, 0);
				if (getr(y, x)=='.') go(bfs, d, y, x+1, h, 0, 0);
			}
			if (di==2){
				if (getb(y, x)=='.') go(bfs, d, y+1, x, h, 0, 0);
				if (getl(y, x)=='.') go(bfs, d, y, x-1, h, 3, 0);
			}
			if (di==3){
				if (getb(y, x)=='.') go(bfs, d, y+1, x, h, 1, 0);
				if (getr(y, x)=='.') go(bfs, d, y, x+1, h, 2, 0);
			}
			
			//katossa liikkuminen
			if (h==3){
				//samassa tilessa
				if (di==0||di==3) {
					go(bfs, d, y, x, h, 2, 1);
					go(bfs, d, y, x, h, 1, 1);
				}
				if (di==1||di==2){
					go(bfs, d, y, x, h, 0, 1);
					go(bfs, d, y, x, h, 3, 1);
				}
			}
			//ovesta
			if (h<3){
				//toiseen tileen
				if (di==0){
					if (gett(y, x)=='D') go(bfs, d, y-1, x, h, 2, 0);
					if (getl(y, x)=='D') go(bfs, d, y, x-1, h, 1, 0);
				}
				if (di==1){
					if (gett(y, x)=='D') go(bfs, d, y-1, x, h, 3, 0);
					if (getr(y, x)=='D') go(bfs, d, y, x+1, h, 0, 0);
				}
				if (di==2){
					if (getb(y, x)=='D') go(bfs, d, y+1, x, h, 0, 0);
					if (getl(y, x)=='D') go(bfs, d, y, x-1, h, 3, 0);
				}
				if (di==3){
					if (getb(y, x)=='D') go(bfs, d, y+1, x, h, 1, 0);
					if (getr(y, x)=='D') go(bfs, d, y, x+1, h, 2, 0);
				}
			}
			//seinaa sivulle
			if (onw){
				//samassa tilessa
				if (di==0){
					if (getl(y, x)=='|') go(bfs, d, y, x, h, 2, 1);
					if (gett(y, x)=='-') go(bfs, d, y, x, h, 1, 1);
				}
				if (di==1){
					if (getr(y, x)=='|') go(bfs, d, y, x, h, 3, 1);
					if (gett(y, x)=='-') go(bfs, d, y, x, h, 0, 1);
				}
				if (di==2){
					if (getl(y, x)=='|') go(bfs, d, y, x, h, 0, 1);
					if (getb(y, x)=='-') go(bfs, d, y, x, h, 3, 1);
				}
				if (di==3){
					if (getr(y, x)=='|') go(bfs, d, y, x, h, 1, 1);
					if (getb(y, x)=='-') go(bfs, d, y, x, h, 2, 1);
				}
				
				//toiseen tileen
				if (di==0){
					if (gett(y, x)=='.') go(bfs, d, y-1, x, h, 2, 0);
					if (getl(y, x)=='.') go(bfs, d, y, x-1, h, 1, 0);
				}
				if (di==1){
					if (gett(y, x)=='.') go(bfs, d, y-1, x, h, 3, 0);
					if (getr(y, x)=='.') go(bfs, d, y, x+1, h, 0, 0);
				}
				if (di==2){
					if (getb(y, x)=='.') go(bfs, d, y+1, x, h, 0, 0);
					if (getl(y, x)=='.') go(bfs, d, y, x-1, h, 3, 0);
				}
				if (di==3){
					if (getb(y, x)=='.') go(bfs, d, y+1, x, h, 1, 0);
					if (getr(y, x)=='.') go(bfs, d, y, x+1, h, 2, 0);
				}
			}
		}
		//cout<<cl.F.F<<" "<<cl.F.S<<" "<<cl.S<<endl;
		cout<<dist[cl.F.F][cl.F.S][0][cl.S]<<'\n';
	}
}