Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

0ms 不虚

Posted by musashi at 2016-04-26 23:18:08 on Problem 1753
#include<cstdio>
#include<cstring>
const int MAXN = 1<<16;
int dis[MAXN], q[MAXN];
int move[]={0xc800,0xe400,0x7200,0x3100,
			0x8c80,0x4e40,0x2720,0x1310,
			0x8c8,0x4e4,0x272,0x131,
			0x8c,0x4e,0x27,0x13};
int Input() {
	char in[6];
	int ret=0;
	for(int i=0; i<4; ++i)
	{
		scanf("%s", in);
		for(int j=0; j<4; ++j)
		{
			ret <<= 1;
			if(in[j]=='b') ret++;
		}
	}
	return ret;
}
int BFS(int s) {
	memset(dis, 0xff, sizeof(dis));
	dis[s] = 0;
	if(s==0||s==MAXN-1)
		return 0;
	int l, r;
	l = r = 0;
	q[r++] = s;
	while(l!=r) {
		int pos = q[l++];
		//printf("step:%d\t%x\n", dis[pos], pos);
		for(int i=0; i<16; ++i)
		{
			int np = pos^move[i];
			if(np==0||np==MAXN-1) {
			//	printf("%d\n", np);
				return dis[np]=dis[pos]+1;
			}
			if(dis[np]==-1) {
				dis[np] = dis[pos]+1;
				q[r++] = np;
				if(r==MAXN) r = 0;
			}
		}
	}
	return -1;
}
int main() {
	int pos = Input();
	int step = BFS(pos);
	if(step!=-1) printf("%d\n", step);
	else puts("Impossible");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator