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

位运算~~~~才学会

Posted by 821388334 at 2013-12-14 13:30:52 on Problem 1753
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#define M 65535
#define N 0
using namespace std;
typedef struct dir{
	int data;
	int step;
}dir;
queue <dir> v;
char map[4][4];
int vis[M + 1];
int bfs(int data){
	int i;
	dir l, p, q;
	l.data = data;
	l.step = 0;
	v.push(l);
	vis[data] = 1;
	while(!v.empty()){
		p = v.front();
		v.pop();
		if(p.data == M || p.data == N){
			return p.step;
		}
		else{
			for(i = 0; i < 16; i++){
				int elem = p.data;
				elem = elem^(1 << i);
				if(i > 3)
					elem = elem^(1 << (i - 4));
				if(i < 12)
					elem = elem^(1 << (i + 4));
				if(i % 4 != 0)
					elem = elem^(1 << (i - 1));
				if(i % 4 != 3)
					elem = elem^(1 << (i + 1));
				q.data = elem;
				q.step = p.step + 1;
				if(!vis[elem]){
					vis[elem] = 1;
					v.push(q);
				}
			}	
		}
	}
	while(!v.empty())
		v.pop();
	return -1;
}

int main(){
	int i, j, data = 0, step = 0;
	for(i = 0; i < 4; i++){
		gets(map[i]);
		for(j = 0; j < 4; j++){
			if(map[i][j] == 'b')
				data = (data << 1) + 1;
			else
				data = data << 1;
		}
	}
	memset(vis, 0, sizeof(vis));
	step = bfs(data);
	if(step == -1)
		printf("Impossible\n");
	else
		printf("%d\n", step);
	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