#include #include #include #include #include using namespace std; typedef struct _node { int cnt; vector dir; _node(): cnt(0) {} }myNode; static int dr[4] = { 0, 0, 1, -1 }; static int dc[4] = { 1, -1, 0, 0 }; void updateRouteMap(int startR, int startC, vector>& routeMap) { routeMap[startR][startC].cnt++; stack> S; S.push(make_pair(startR, startC)); vector::iterator it; while (!S.empty()) { int currR = S.top().first; int currC = S.top().second; S.pop(); for (it = routeMap[currR][currC].dir.begin(); it < routeMap[currR][currC].dir.end(); it++) { int nr = currR + dr[*it]; int nc = currC + dc[*it]; routeMap[nr][nc].cnt++; S.push(make_pair(nr, nc)); } } } int BFS(int targetR, int targetC, vector>& myMap) { queue> Q; Q.push(make_pair(1, 1)); vector> routeMap(myMap.size(), vector(myMap[0].size())); int breadth = 0; int minRequireMove = targetR + targetC - 2; while(!Q.empty()) { if (breadth == 0) { breadth = Q.size(); minRequireMove--; } int currR = Q.front().first; int currC = Q.front().second; Q.pop(); breadth--; for (int i = 0; i < 4; i++) { int nr = currR + dr[i]; int nc = currC + dc[i]; if (myMap[currR][currC] <= myMap[nr][nc] || myMap[targetR][targetC] + minRequireMove > myMap[nr][nc]) continue; if (routeMap[nr][nc].cnt >= 1) { updateRouteMap(nr, nc, routeMap); continue; } if (nr == targetR && nc == targetC) { routeMap[nr][nc].cnt = 1; routeMap[currC][currR].dir.push_back(i); continue; } Q.push(make_pair(nr, nc)); routeMap[nr][nc].cnt = routeMap[currC][currR].cnt; routeMap[currC][currR].dir.push_back(i); } } return routeMap[targetR][targetC].cnt; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int M, N; cin >> M >> N; vector> myMap(M + 2, vector(N + 2, INT_MAX)); for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { int input; cin >> input; myMap[i][j] = input; } } cout << BFS(M, N, myMap); return 0; }

제출 #163091

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: