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