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 |
今天自学BFS。。。都不知道在说什么,然后写的程序就过了= =这尼玛太假了#include<iostream> #include<queue> using namespace std; #include<memory.h> #define maxn 1000 int end_x,end_y; int l; struct node { int x,y; int step; }; bool vis[maxn][maxn]; int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}}; int bfs(int x,int y) { int d; memset(vis,false,sizeof(vis)); queue<node>q; node cur,next; cur.x = x; cur.y = y; cur.step = 0; q.push(cur); vis[x][y] = true; while(!q.empty()) { cur = q.front(); q.pop(); if(x == end_x && y == end_y) return cur.step; for(d = 0; d < 8;d++) { next.x = cur.x + dir[d][0]; next.y = cur.y + dir[d][1]; if(next.x >= 0 && next.y >= 0 && next.x <= l-1 && next.y <= l-1 && !vis[next.x][next.y]) { next.step = cur.step + 1; if(end_x == next.x && end_y == next.y) return next.step; vis[next.x][next.y] = true; q.push(next); } } } return -1; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int n; int step; int start_x,start_y; cin >> n; for(int i = 0; i < n;i++) { cin >> l; cin >> start_x >> start_y; cin >> end_x >> end_y; step = bfs(start_x,start_y); cout << step << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator