Go to diff to previous submission
#include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <utility> #include <stack> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <list> #define SIZEOF(a) (sizeof(a)/sizeof(a[0])) #define FILL(a,b) fill(a,a+SIZEOF(a),b) #define FOR(a,b,c) for(int a=b;a<=c;a++) #define FORARR(i,a) for(unsigned i=0; i<SIZEOF(a); i++) #define FOREACH(a,b) for(__typeof((b).begin()) a = (b).begin(); a!=(b).end(); a++) #define GETI(a) scanf("%d ", &a); #define SWAP(a,b) { __typeof(a) t = a; a = t; b = t; } using namespace std; struct coords { int x,y; coords(int x, int y) : x(x),y(y) {} }; int main(void) { int R,C; cin >> R >> C; int startX, startY; cin >> startX >> startY; int endX, endY; cin >> endX >> endY; while (!feof(stdin)) { vector<vector<int> > visited(max(R,C)+1, vector<int>(max(R,C)+1,-1)); visited[startX][startY] = 0; queue<coords> q; q.push(coords(startX, startY)); if (startX == endX && startY == endY) { cout << 0 << endl; goto out; } while (!q.empty()) { coords c = q.front(); q.pop(); // cerr << "at " << c.x << " " << c.y << endl; coords nbs[] = { coords(c.x-1, c.y-2), coords(c.x-1, c.y+2), coords(c.x+1, c.y-2), coords(c.x+1, c.y+2), coords(c.x-2, c.y-1), coords(c.x-2, c.y+1), coords(c.x+2, c.y-1), coords(c.x+2, c.y+1), }; FORARR(i,nbs) { coords nb = nbs[i]; // validate... if (nb.x < 1 || nb.x > R || nb.y < 1 || nb.y > C) continue; // bad if (visited[nb.x][nb.y] != -1) continue; visited[nb.x][nb.y] = visited[c.x][c.y] + 1; if (nb.x == endX && nb.y == endY) { // victory! cout << visited[nb.x][nb.y] << endl; goto out; } q.push(nb); } } cout << "impossible" << endl; out: cin >> R >> C; cin >> startX >> startY; cin >> endX >> endY; } return 0; }
--- c4.s597.cteam092.grasshop.cpp.0.g.cpp +++ c4.s619.cteam092.grasshop.cpp.0.g.cpp @@ -44,4 +44,5 @@ while (!feof(stdin)) { + vector<vector<int> > visited(max(R,C)+1, vector<int>(max(R,C)+1,-1)); visited[startX][startY] = 0; @@ -50,4 +51,9 @@ q.push(coords(startX, startY)); + if (startX == endX && startY == endY) { + cout << 0 << endl; + goto out; + } + while (!q.empty()) { coords c = q.front(); @@ -69,5 +75,5 @@ if (nb.x < 1 || nb.x > R || nb.y < 1 || nb.y > C) continue; // bad - if (visited[nb.x][nb.y] > 0) continue; + if (visited[nb.x][nb.y] != -1) continue; visited[nb.x][nb.y] = visited[c.x][c.y] + 1; if (nb.x == endX && nb.y == endY) { @@ -83,5 +89,5 @@ cout << "impossible" << endl; -out: {} +out: cin >> R >> C; cin >> startX >> startY;