题解 P2226 【[HNOI2001]遥控赛车比赛】

· · 题解

(哇一道大水题没有人发题解)

这道题。。。

怎么说呢

实际上很简单，就和直接看上去一样，相信大家都会认为这是一道爆搜题。。

所以我索性就打了一个DFS。。

(代码略丑，不喜勿喷)

#include <bits/stdc++.h>

using namespace std;

const int fx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int N = 100;

int n;
int m;
int Fx;
int Fy;
int Tx;
int Ty;
int res;
int s[N + 1][N + 1];
int rem[2][N + 1][N + 1];

bool remem(int x, int y, int tot, int k) {
    if(tot > rem[0][x][y]) return 1;
    else if(tot < rem[0][x][y]) return 0;
    else return k <= rem[1][x][y];
}

void dfs(int x, int y, int k, int maxn, int tot, int la) {
    if(!s[x][y] || x < 1 || y < 1 || x > n || y > m || remem(x, y, tot, k)) return;
    rem[0][x][y] = tot;
    rem[1][x][y] = k;
    if(x == Tx && y == Ty) {
        if(res < 0) res = tot;
        else res = min(res, tot);
        return;
    }
    for(int i = 0; i < 4; i++)
        if(i != la) {
            if(k == maxn)
                dfs(x + fx[i][0], y + fx[i][1], 1, maxn, tot + 1, i);
        }
        else dfs(x + fx[i][0], y + fx[i][1], min(k + 1, maxn), maxn, tot + 1, i);
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &Fx, &Fy, &Tx, &Ty);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);
    for(int i = 1; i <= 10; i++) {
        res = -1;
        memset(rem[0], 127, sizeof(rem[0]));
        memset(rem[1], 0, sizeof(rem[1]));
        dfs(Fx, Fy, i, i, 0, -1);
        if(res == -1) break;
        printf("%d %d\n", i, res);
    }
    return 0;
}

就像这样。。

然后30分，WA与TLE并存。。。

不明所以的我认为是DFS的锅，然后改了一个BFS。。

再贴一波：

#include <bits/stdc++.h>

using namespace std;

const int fx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int N = 100;

int n;
int m;
int Fx;
int Fy;
int Tx;
int Ty;
int res;
int s[N + 1][N + 1];
int f[N + 1][N + 1][4];
int dis[N + 1][N + 1][4];

struct Node {
    int x;
    int y;
    int z;
};

void print() {/*
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            printf("%-3d ", dis[i][j]);
        puts("");
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            printf("%-3d ", f[i][j]);
        puts("");
    }*/
}

void BFS(int k) {
    queue<Node>q;
    while(!q.empty()) q.pop();
    q.push((Node){Fx, Fy, 0});
    q.push((Node){Fx, Fy, 1});
    q.push((Node){Fx, Fy, 2});
    q.push((Node){Fx, Fy, 3});
    f[Fx][Fy][0] = 0;
    f[Fx][Fy][1] = 0;
    f[Fx][Fy][2] = 0;
    f[Fx][Fy][3] = 0;
    while(!q.empty()) {
        Node now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int x = now.x + fx[i][0];
            int y = now.y + fx[i][1];
            if(x > n || y > m || x < 1 || y < 1) continue;
            if(dis[x][y][i] || !s[x][y] || (x == Fx && y == Fy)) continue;
            if(i == now.z)
                f[x][y][i] = min(k, f[now.x][now.y][now.z] + 1);
            else {
                if(f[now.x][now.y][now.z] != k) continue;
                f[x][y][i] = 1;
            }
            q.push((Node){x, y, i});
            dis[x][y][i] = dis[now.x][now.y][now.z] + 1;
            if(x == Tx && y == Ty) {
                res = dis[x][y][i];
                return ;
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &Fx, &Fy, &Tx, &Ty);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);
    for(int i = 1; i <= 10; i++) {
        res = -1;
        memset(f, 0, sizeof(f));
        memset(dis, 0, sizeof(dis));
        BFS(i);
        print();
        if(res == -1) break;
        printf("%d %d\n", i, res);
    }
    return 0;
}

结果还是40分。。。

真是可怕。。。

但是至少没有TLE了。。

然后我就一直找啊找，发现了一个灵异事件：

之前你可能有一个弯绕不过去，

但是有可能你从别的地方绕一下再来这个点的时候就可以过了

上样例：

input：
10 5
4 2 10 3
1 1 1 1 1
0 1 0 0 1
0 1 0 1 1
1 1 0 1 1 
0 1 1 1 1
1 1 1 1 0
1 1 1 1 1
0 0 1 0 1
0 0 1 0 1
0 0 1 0 1

output：
7
11

你的代码是不是输出：

7
17

这就是我要说的了

实际上它是这么搞的：

来回走很骚对吧。。

但是并不需要担心复杂度

中间只需要加上一个判断就好

代码中会有提到：

#include <bits/stdc++.h>

using namespace std;

const int fx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int N = 100;

int n;
int m;
int Fx;
int Fy;
int Tx;
int Ty;
int res;
int s[N + 1][N + 1];
int f[N + 1][N + 1][4];
int dis[N + 1][N + 1][4];

struct Node {
    int x;
    int y;
    int z;
};

void print() {/*
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            printf("%-3d ", dis[i][j]);
        puts("");
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            printf("%-3d ", f[i][j]);
        puts("");
    }*/
}

void BFS(int k) {
    queue<Node>q;
    while(!q.empty()) q.pop();
    q.push((Node){Fx, Fy, 0});
    q.push((Node){Fx, Fy, 1});
    q.push((Node){Fx, Fy, 2});
    q.push((Node){Fx, Fy, 3});
    f[Fx][Fy][0] = 0;
    f[Fx][Fy][1] = 0;
    f[Fx][Fy][2] = 0;
    f[Fx][Fy][3] = 0;//0、1、2、3表示从哪个方向来的，f记录连续走了多少步
    while(!q.empty()) {
        Node now = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            int x = now.x + fx[i][0];
            int y = now.y + fx[i][1];
            if(x > n || y > m || x < 1 || y < 1) continue;
            if(!s[x][y] || (x == Fx && y == Fy)) continue;
            int a;
            if(i == now.z)
                a = min(k, f[now.x][now.y][now.z] + 1);
            else {
                if(f[now.x][now.y][now.z] != k) continue;
                a = 1;
            }
            if(dis[x][y][i] && a <= f[x][y][i]) continue;
            //之前提到的就是这里了
            //这里是说如果之前到过并且连续走的步数比之前记录的少就放弃
            f[x][y][i] = a;
            q.push((Node){x, y, i});
            dis[x][y][i] = dis[now.x][now.y][now.z] + 1;
            if(x == Tx && y == Ty) {
                res = dis[x][y][i];
                return ;
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &Fx, &Fy, &Tx, &Ty);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &s[i][j]);
    for(int i = 1; i <= 10; i++) {
        res = -1;
        memset(f, 0, sizeof(f));
        memset(dis, 0, sizeof(dis));
        BFS(i);
        print();
        if(res == -1) break;
        printf("%d %d\n", i, res);
    }
    return 0;
}

嗯，这样就可以AC了