| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
位运算~~~~才学会#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator