学步园

#include <iostream><br /> #include <queue><br /> using namespace std;<br /> class P<br /> {<br /> public:<br /> int x;<br /> int y;<br /> int d;<br /> P(int x = -1, int y = -1, int d = 0):x(x),y(y),d(d){}<br /> /*<br /> P& operator=(const P& p1)<br /> {<br /> x = p1.x;<br /> y = p1.y;<br /> d = p1.d;<br /> return *this;<br /> }<br /> */<br /> };<br /> queue<P> q;<br /> const int N = 300;<br /> int n;<br /> int l;<br /> int sx, sy;<br /> int ex, ey;<br /> int hash[300][300];<br /> int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};<br /> int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};<br /> void BFS()<br /> {<br /> int x, y;<br /> P p;<br /> while(!q.empty())<br /> {<br /> p = q.front();<br /> q.pop();<br /> if(p.x == ex && p.y == ey)<br /> {<br /> cout << p.d << endl;<br /> return;<br /> } </p> <p> for(int i = 0; i < 8; i++)<br /> {<br /> x = p.x + mx[i];<br /> y = p.y + my[i];<br /> if( x < 0 || y < 0 || x >= l || y >= l)<br /> {<br /> continue;<br /> }<br /> if(!hash[x][y])<br /> {<br /> hash[x][y] = 1;<br /> q.push(P(x, y, p.d + 1));<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> cin >> n;<br /> for(int i = 0; i < n; i++)<br /> {<br /> cin >> l;<br /> cin >> sx >> sy;<br /> cin >> ex >> ey;<br /> for(int j = 0; j < l; j++)<br /> {<br /> for(int k = 0; k < l; k++)<br /> {<br /> hash[j][k] = 0;<br /> }<br /> }<br /> while(!q.empty())<br /> {<br /> q.pop();<br /> }<br /> q.push(P(sx, sy, 0));<br /> BFS();<br /> }<br /> }