Usaco Training Section 5.2 Snail Trails

這……不是普及組難度的題嗎？作為5.2的唯一一題有點水了吧。

直接dfs，按題意模拟，不用優化。

一開始沒注意障礙物的橫坐标可能會是多位數。其他就沒什麼坑了吧。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;

int n,b,ans,v[4][2]={-1,0,1,0,0,-1,0,1};
bool vis[125][125],a[125][125];

inline void dfs(int x,int y,int d,int step){
	int x2=x+v[d][0],y2=y+v[d][1];
	if(x2>0&&x2<=n&&y2>0&&y2<=n&&!vis[x2][y2]&&!a[x2][y2]){
		vis[x2][y2]=1;
		dfs(x2,y2,d,step+1);
		vis[x2][y2]=0;
	}
	else if(x2<=0||x2>n||y2<=0||y2>n||a[x2][y2]){
		int d1,d2;
		if(d==0||d==1) d1=2,d2=3;
		else d1=0,d2=1;
		bool f=0;
		x2=x+v[d1][0],y2=y+v[d1][1];
		if(x2>0&&x2<=n&&y2>0&&y2<=n&&!vis[x2][y2]&&!a[x2][y2]){
			f=1;
			vis[x2][y2]=1;
			dfs(x2,y2,d1,step+1);
			vis[x2][y2]=0;
		}
		x2=x+v[d2][0],y2=y+v[d2][1];
		if(x2>0&&x2<=n&&y2>0&&y2<=n&&!vis[x2][y2]&&!a[x2][y2]){
			f=1;
			vis[x2][y2]=1;
			dfs(x2,y2,d2,step+1);
			vis[x2][y2]=0;
		}
		if(!f){
			ans=max(ans,step);
			return;
		}
	}
	else{
		ans=max(ans,step);
		return;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("snail.in","r",stdin);
	freopen("snail.out","w",stdout);
	cin>>n>>b;
	for(int i=1;i<=b;++i){
		string s;
		cin>>s;
		int y=s[0]-64,l=s.length(),x=0;
		for(int j=1;j<l;++j) x=x*10+(s[j]^48);
		a[x][y]=1;
	}
	vis[1][1]=1;
	dfs(1,1,3,1);
	dfs(1,1,1,1);
	cout<<ans<<'\n';
	return 0;
}