傳送門
暴力+搜索
手動打表它不香嗎【逃~~
首先想到用dfs來遍歷煙花分支，用一張表來標記是否經過點，煙花一共有8個方向，而且很容易想到每一個方向過后都只有兩個固定的方向可以選擇，因此本題可以列舉8個方向之后的2種可能來解決，
煙花可能會向四面八方綻開，如果原點為[0,0]，坐標可能會有負數，因此我們需要每次在表上操作時對坐標加一個偏移值，因為n<=30,ti<=5,所以最多向一個方向移動150個單位，偏移值為150，標記表開為300*300
需要注意的是，可能有同時在同一位置，同一方向的分支產生，這時需要記憶化，否則會超時QAQ
code:
#include<bits/stdc++.h> using namespace std; const int M=150; int n,a[35],Map[305][305],ans,f[35][305][305][3][3]; void dfs(int step,int x,int y,int p,int q){//當前是第step層，開始坐標為[x,y] //x軸方向為p，y軸方向為q(用-1，1，0表示，x軸和y軸方向是陣列存盤順序) if(f[step][x][y][p+1][q+1]) return; f[step][x][y][p+1][q+1]=1;//記憶化剪枝 if(step>n) return;//層數到n+1退出 int len=a[step];//每次走的長度 for(int i=1;i<=len;i++){ x+=p; y+=q;//坐標更新 Map[x][y]=1;//每一步都標記 } int xx,yy;//表示下一步的方向 if(p==-1&&q==0) xx=-1,yy=-1; else if(p==-1&&q==-1) xx=0,yy=-1; else if(p==0&&q==-1) xx=1,yy=-1; else if(p==1&&q==-1) xx=1,yy=0; else if(p==1&&q==0) xx=1,yy=1; else if(p==1&&q==1) xx=0,yy=1; else if(p==0&&q==1) xx=-1,yy=1; else if(p==-1&&q==1) xx=-1,yy=0; dfs(step+1,x,y,xx,yy);//分支1 if(p==-1&&q==0) xx=-1,yy=1; else if(p==-1&&q==1) xx=0,yy=1; else if(p==0&&q==1) xx=1,yy=1; else if(p==1&&q==1) xx=1,yy=0; else if(p==1&&q==0) xx=1,yy=-1; else if(p==1&&q==-1) xx=0,yy=-1; else if(p==0&&q==-1) xx=-1,yy=-1; else if(p==-1&&q==-1) xx=-1,yy=0; dfs(step+1,x,y,xx,yy);//分支2 } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dfs(1,M,M,-1,0);//注意起始坐標為[M,M] for(int i=0;i<=300;i++) for(int j=0;j<=300;j++) ans+=Map[i][j];//遍歷標記表 printf("%d",ans); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77807.html
標籤：其他
上一篇：演算法題輕松決議——匯總