洛谷 P1560 [USACO5.2]蜗牛的旅行Snail Trails

题目链接

题解

一看题没什么思路。写了个暴力居然可过？！

Code

#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
inline int gi() {
    bool f = 0; char c = getchar();
    RG int x = 0;
    while (c!='-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') f = 1, c = getchar();
    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
    return f ? -x:x;
}
const int N = 210;
bool a[N][N], vis[N][N];
int mv[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, ans;

void dfs(int x, int y, int d, int z) {
    int xx = x+mv[d][0], yy = y+mv[d][1];
    if (vis[xx][yy]) {
        ans = max(ans, z);
        return ;
    }
    if (!a[xx][yy]) {
        vis[xx][yy] = 1;
        dfs(xx, yy, d, z+1);
        vis[xx][yy] = 0;
    }
    else {
        int dd = (d+1)%4;
        bool flag = 0;
        xx = x+mv[dd][0], yy = y+mv[dd][1];
        if (!a[xx][yy] && !vis[xx][yy]) {
            vis[xx][yy] = 1;
            flag = 1, dfs(xx, yy, dd, z+1);
            vis[xx][yy] = 0;
        }
        dd = (d+3)%4;
        xx = x+mv[dd][0], yy = y+mv[dd][1];
        if (!a[xx][yy] && !vis[xx][yy]) {
            vis[xx][yy] = 1;
            flag = 1, dfs(xx, yy, dd, z+1);
            vis[xx][yy] = 0;
        }
        if (!flag) ans = max(ans, z);
    } 
    return ;
}

int main() {
    int n = gi(), ss = gi(), x;
    char s;
    for (int i = 1; i <= ss; i++) {
        cin >> s >> x;
        a[x][s-'A'+1] = 1;
    }
    for (int i = 1; i <= n; i++)
        a[0][i] = a[i][0] = a[n+1][i] = a[i][n+1] = 1;
/*  for (int i = 0; i <= n+1; i++, printf("\n"))
        for (int j = 0; j <= n+1; j++)
            printf("%d ", a[i][j]);*/
    vis[1][1] = 1;
    dfs(1, 1, 0, 1);
    dfs(1, 1, 1, 1);
    printf("%d\n", ans);
    return 0;
}

洛谷 P1560 [USACO5.2]蜗牛的旅行Snail Trails

原文：https://www.cnblogs.com/zzy2005/p/9912078.html