QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39640#2932. Checker SlideLangdao_ZhangAC ✓109ms8312kbC++4.4kb2022-07-12 16:58:252022-07-12 16:58:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-12 16:58:28]
  • 评测
  • 测评结果：AC
  • 用时：109ms
  • 内存：8312kb
查看
  • [2022-07-12 16:58:25]
  • 提交

answer

#include<iostream>
#include<string.h>
#include<map>
#include<set>
#include<deque>

#define lint int64_t

using
		namespace
					std;

class Config{
	
	public:
		
		bool a[6][6];
		int x[4],y[4];
		
		Config(){
			
			memset(a,false,sizeof(a));
		}
		
		bool __equal(Config& B){
			
			return c2i(*this)==c2i(B);
		}
		
		void print(){
			
			for(int i=0;i<6;i++){
				
				for(int j=0;j<6;j++){
					
					putchar(a[i][j]?'*':'_');
				}
				putchar('\n');
			}
			putchar('\n');
		}
		
		friend lint c2i(Config& c);
	
};

class Mpace{
	
	public:
		
		int xs,ys,xt,yt;
		
		Mpace(int xs_=0,int ys_=0,int xt_=0,int yt_=0){
			
			xs=xs_,ys=ys_,xt=xt_,yt=yt_;
		}
};

lint c2i(Config& c){
	
	lint ans=0;
	
	for(int i=0;i<6;i++){
		
		for(int j=0;j<6;j++){
			
			ans+=c.a[i][j];
			ans<<=1;
		}
	}
	
	return ans;
}

Config _move(Config now,int i,int dx,int dy){
	
	if(dx==-1&&dy==0){
		
		int nxtx=0;
		
		for(int k=0;k<4;k++){
			
			if(now.x[k]<now.x[i]&&now.y[k]==now.y[i]){
				
				nxtx=max(nxtx,now.x[k]+1);
			}
		}
		
		now.a[now.x[i]][now.y[i]]=false;
		now.a[nxtx][now.y[i]]=true;
		now.x[i]=nxtx;
	}
	else if(dx==1&&dy==0){
		
		int nxtx=5;
		
		for(int k=0;k<4;k++){
			
			if(now.x[k]>now.x[i]&&now.y[k]==now.y[i]){
				
				nxtx=min(nxtx,now.x[k]-1);
			}
		}
		
		now.a[now.x[i]][now.y[i]]=false;
		now.a[nxtx][now.y[i]]=true;
		now.x[i]=nxtx;
	}
	else if(dx==0&&dy==-1){
		
		int nxty=0;
		
		for(int k=0;k<4;k++){
			
			if(now.y[k]<now.y[i]&&now.x[k]==now.x[i]){
				
				nxty=max(nxty,now.y[k]+1);
			}
		}
		
		now.a[now.x[i]][now.y[i]]=false;
		now.a[now.x[i]][nxty]=true;
		now.y[i]=nxty;
	}
	else if(dx==0&&dy==1){
		
		int nxty=5;
		
		for(int k=0;k<4;k++){
			
			if(now.y[k]>now.y[i]&&now.x[k]==now.x[i]){
				
				nxty=min(nxty,now.y[k]-1);
			}
		}
		
		now.a[now.x[i]][now.y[i]]=false;
		now.a[now.x[i]][nxty]=true;
		now.y[i]=nxty;
	}
	
	return now;
}

Config S,T;
deque<Mpace> kotae;
map<lint,lint> pre;
map<lint,Mpace> sousa;

void bfs(){
	
	deque<Config> q;
	
	q.push_back(S);
	
	pre[c2i(S)]=-1;
	
	while(!q.empty()){
		
		Config now=q.front();
		
//		for(int i=0;i<6;i++){
//			
//			for(int j=0;j<6;j++){
//				
//				putchar(now.a[i][j]?'*':'_');
//			}
//			putchar('\n');
//		}
//		putchar('\n');
		
//		if(now.a[2][2]&&now.a[3][2]&&now.a[4][2]&&now.a[5][5]){
//			
//			printf("^-^\n");
//			
//			for(int i=0;i<4;i++){
//				
//				cout<<now.x[i]<<' '<<now.y[i]<<endl;
//			}
//		}
		
		lint id=c2i(now);
		
		q.pop_front();
		
		if(now.__equal(T)){
			
			return;
		}
		
		Config nxt;
		lint idnxt;
		
		for(int i=0;i<4;i++){
			
			nxt=_move(now,i,-1,0);
			
			idnxt=c2i(nxt);
			
			if(pre.find(idnxt)==pre.end()){
				
				q.push_back(nxt);
				pre[idnxt]=id;
				sousa[idnxt]=Mpace(now.x[i],now.y[i],nxt.x[i],nxt.y[i]);
				if(nxt.__equal(T)) return;
			}
			
			nxt=_move(now,i,1,0);
			
			idnxt=c2i(nxt);
			
			if(pre.find(idnxt)==pre.end()){
				
				q.push_back(nxt);
				pre[idnxt]=id;
				sousa[idnxt]=Mpace(now.x[i],now.y[i],nxt.x[i],nxt.y[i]);
				if(nxt.__equal(T)) return;
			}
			
			nxt=_move(now,i,0,-1);
			
			idnxt=c2i(nxt);
			
			if(pre.find(idnxt)==pre.end()){
				
				q.push_back(nxt);
				pre[idnxt]=id;
				sousa[idnxt]=Mpace(now.x[i],now.y[i],nxt.x[i],nxt.y[i]);
				if(nxt.__equal(T)) return;
			}
			
			nxt=_move(now,i,0,1);
			
			idnxt=c2i(nxt);
			
			if(pre.find(idnxt)==pre.end()){
				
				q.push_back(nxt);
				pre[idnxt]=id;
				sousa[idnxt]=Mpace(now.x[i],now.y[i],nxt.x[i],nxt.y[i]);
				if(nxt.__equal(T)) return;
			}
		}
	}
}

signed main(){
	
	int u,v;
	
	for(int i=0;i<4;i++){
		
		cin>>u>>v;
		S.a[u][v]=true;
		S.x[i]=u;
		S.y[i]=v;
	}
	
	for(int i=0;i<4;i++){
		
		cin>>u>>v;
		T.a[u][v]=true;
		T.x[i]=u;
		T.y[i]=v;
	}
	
	bfs();
	
	lint iS=c2i(S);
	
	for(lint now=c2i(T);now!=iS;now=pre[now]){
		
		kotae.push_front(sousa[now]);
	}
	
	cout<<kotae.size()<<endl;
	
	for(Mpace& it:kotae){
		
		cout<<it.xs<<' '<<it.ys<<' '<<it.xt<<' '<<it.yt<<endl;
	}
	
end:
	return EOF+1;
}
/*
5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

2 2 2 3 3 2 3 3
0 0 0 5 5 0 5 5

0 0 3 4 5 3 1 2
0 0 3 4 5 3 1 2

1 2 2 2 3 2 4 2
2 2 3 2 4 2 5 2

1 2 2 2 3 2 4 2
1 2 2 2 3 2 5 5

0 0 0 5 5 0 5 5
0 0 0 1 0 2 0 3

2 2 2 3 3 2 3 3
1 1 1 2 2 1 5 5
*/
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 31ms
memory: 5676kb

input:

5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

output:

12
5 0 1 0
0 5 4 5
0 0 0 5
4 5 1 5
5 5 2 5
1 5 1 1
0 5 1 5
1 5 1 2
1 1 5 1
1 0 1 1
5 1 2 1
2 5 2 2

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 99ms
memory: 8140kb

input:

3 2 2 1 1 0 0 3
4 3 3 5 1 3 0 4

output:

18
3 2 5 2
2 1 2 5
2 5 5 5
5 5 5 3
5 2 5 0
5 3 1 3
1 0 4 0
0 3 0 0
0 0 3 0
4 0 4 5
5 0 4 0
4 0 4 4
4 5 5 5
5 5 5 0
5 0 4 0
4 0 4 3
4 4 0 4
3 0 3 5

result:

ok correct plan

Test #3:

score: 0
Accepted
time: 3ms
memory: 3728kb

input:

5 5 3 4 2 0 0 2
3 4 3 0 0 2 0 1

output:

4
5 5 5 0
5 0 3 0
2 0 0 0
0 0 0 1

result:

ok correct plan

Test #4:

score: 0
Accepted
time: 6ms
memory: 4104kb

input:

3 5 2 1 1 5 0 3
2 2 1 3 1 2 0 1

output:

6
3 5 2 5
2 5 2 2
2 1 0 1
0 3 0 2
0 2 1 2
1 5 1 3

result:

ok correct plan

Test #5:

score: 0
Accepted
time: 16ms
memory: 5356kb

input:

2 2 1 5 0 3 0 1
2 2 1 4 0 3 0 1

output:

8
0 3 0 2
0 2 1 2
1 2 1 4
1 5 0 5
0 5 0 2
0 2 1 2
1 2 1 3
1 3 0 3

result:

ok correct plan

Test #6:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

5 0 4 5 3 0 1 0
4 4 4 0 3 5 1 0

output:

6
5 0 4 0
4 0 4 4
4 5 5 5
5 5 5 0
5 0 4 0
3 0 3 5

result:

ok correct plan

Test #7:

score: 0
Accepted
time: 100ms
memory: 8092kb

input:

5 3 4 3 1 4 1 2
3 4 3 2 2 2 0 1

output:

18
5 3 5 0
5 0 0 0
1 4 1 3
1 3 3 3
4 3 4 0
0 0 3 0
3 0 3 2
4 0 0 0
3 3 3 5
1 2 0 2
0 0 0 1
0 1 5 1
0 2 2 2
3 2 3 4
3 5 5 5
5 5 5 2
5 1 0 1
5 2 3 2

result:

ok correct plan

Test #8:

score: 0
Accepted
time: 109ms
memory: 8312kb

input:

1 5 1 4 1 3 1 0
5 3 5 2 3 4 3 1

output:

20
1 5 5 5
1 3 5 3
5 5 5 4
5 4 2 4
1 4 1 1
1 0 5 0
5 3 5 1
5 1 2 1
1 1 1 5
1 5 5 5
5 5 5 1
5 1 3 1
2 1 2 3
5 0 5 5
2 3 5 3
5 5 5 4
5 4 3 4
2 4 2 0
2 0 5 0
5 0 5 2

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 105ms
memory: 8240kb

input:

3 4 3 3 3 1 2 3
5 1 1 4 1 1 0 2

output:

16
3 4 0 4
3 3 5 3
5 3 5 5
3 1 0 1
2 3 5 3
5 5 5 4
5 4 1 4
0 4 0 2
5 3 5 0
0 2 5 2
5 0 5 1
5 1 1 1
0 1 0 0
0 0 5 0
5 0 5 1
5 2 0 2

result:

ok correct plan

Test #10:

score: 0
Accepted
time: 5ms
memory: 4084kb

input:

3 2 2 0 0 2 0 1
2 1 1 0 0 2 0 1

output:

5
0 2 2 2
2 0 2 1
2 2 0 2
3 2 1 2
1 2 1 0

result:

ok correct plan

Test #11:

score: 0
Accepted
time: 11ms
memory: 4636kb

input:

3 2 3 1 2 3 0 4
3 2 1 2 0 3 0 2

output:

6
3 1 0 1
0 4 0 2
2 3 0 3
0 2 2 2
0 1 0 2
2 2 1 2

result:

ok correct plan

Test #12:

score: 0
Accepted
time: 9ms
memory: 4464kb

input:

3 1 2 3 1 2 0 2
5 0 2 1 1 2 1 1

output:

6
2 3 2 0
0 2 0 0
2 0 1 0
1 0 1 1
3 1 2 1
0 0 5 0

result:

ok correct plan

Test #13:

score: 0
Accepted
time: 19ms
memory: 5616kb

input:

3 3 3 1 2 3 0 4
2 0 1 5 1 0 0 3

output:

7
3 1 3 0
0 4 0 0
3 0 1 0
1 0 1 5
2 3 2 0
3 3 0 3
0 0 1 0

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 102ms
memory: 8068kb

input:

3 1 2 2 1 3 0 1
4 4 3 2 2 3 0 0

output:

18
3 1 1 1
1 1 1 2
2 2 5 2
1 2 4 2
1 3 0 3
0 1 0 2
0 2 3 2
4 2 4 5
5 2 4 2
4 2 4 4
4 5 0 5
0 5 0 4
0 4 3 4
3 4 3 3
0 3 2 3
3 3 5 3
5 3 5 0
5 0 0 0

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 7ms
memory: 4780kb

input:

5 3 3 1 2 5 2 4
3 4 0 4 0 2 0 1

output:

7
3 1 0 1
2 5 5 5
5 3 5 4
5 4 3 4
5 5 0 5
0 5 0 2
2 4 0 4

result:

ok correct plan
English 繁體中文 简体中文

Server Time: 2024-11-29 22:28:22 | OpenSource Project