广搜30分,判断拐弯出错,求dalao改错

P1649 [USACO07OCT] Obstacle Course S

御坂19000号 @ 2018-08-02 14:57:57

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int turn[N][N],vis[N][N],n,fx,fy,lx,ly,pre[N][N];
char graph[N][N];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
inline int read(){
    int f = 0,x = 0;char ch;
    do{ch = getchar();f |= (ch == '-');}while(!isdigit(ch));
    do{x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar();}while(isdigit(ch));
    return f ? -x : x;
}
inline bool check(int x,int y){
    return (x > 0 && x <= n && y > 0 && y <= n) ? 1 : 0;
}
inline void bfs(int x,int y){
    queue<pair<int,int> > q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        pair<int,int> u = q.front();
        q.pop();
        if(u.first == lx && u.second == ly){
            printf("%d",turn[lx][ly]);
            exit(0);
        }
        for(register int i = 0;i < 4;++i){
            int nextx = u.first + dx[i],nexty = u.second + dy[i];
            if(check(nextx,nexty) && !vis[nextx][nexty] && graph[nextx][nexty] != 'x'){
                vis[nextx][nexty] = 1;
                if(i < 2){
                    if(pre[u.first][u.second] >= 2 || pre[u.first][u.second] == -1){
                        turn[nextx][nexty] = turn[u.first][u.second] + 1;
                    }
                    else{
                        turn[nextx][nexty] = turn[u.first][u.second];
                    }
                    pre[nextx][nexty] = i;
                }
                if(i >= 2){
                    if(pre[u.first][u.second] < 2 || pre[u.first][u.second] == -1){
                        turn[nextx][nexty] = turn[u.first][u.second] + 1;
                    }
                    else{
                        turn[nextx][nexty] = turn[u.first][u.second];
                    }
                    pre[nextx][nexty] = i;
                }
                q.push(make_pair(nextx,nexty));
            }
        }
    }
}
int main(){
    n = read();
    for(register int i = 1;i <= n;++i){
        for(register int j = 1;j <= n;++j){
            cin >> graph[i][j];
        }
    }

    /*for(register int i = 1;i <= n;++i){
        for(register int j = 1;j <= n;++j){
            cout << graph[i][j] << ' ';
        }
        putchar('\n');
    }*/

    for(register int i = 1;i <= n;++i){
        for(register int j = 1;j <= n;++j){
            if(graph[i][j] == 'A')fx = i,fy = j;
            if(graph[i][j] == 'B')lx = i,ly = j;
       }
    }
    //cout << fx << ' ' << fy << ' ' << lx << ' ' << ly << endl;
    pre[fx][fy] = -1;
    turn[fx][fy] = -1;
    vis[fx][fy] = 1;
    bfs(fx,fy);
    /*for(register int i = 1;i <= n;++i){
        for(register int j = 1;j <= n;++j){
            cout << turn[i][j] << ' ';
        }
        putchar('\n');
    }*/
    puts("-1");
    return 0;
}

|