#include#include #include using namespace std;int T,n,m,ans,cnt;int a[10][10];int vis[10][10];int dx[9]={ 0,1,1,1,0,0,-1,-1,-1},dy[9]={ 0,1,-1,0,-1,1,0,1,-1};inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}void dfs(int x,int y,int sum){ if(y>m){x++;y=1;} if(x>n){ans=max(ans,sum);return;} if(!vis[x][y]) { for(int i=1;i<9;i++) vis[x+dx[i]][y+dy[i]]++; dfs(x,y+2,a[x][y]+sum); for(int i=1;i<9;i++) vis[x+dx[i]][y+dy[i]]--; } dfs(x,y+1,sum);}int main(){ T=read(); while(T--) { n=read();m=read();ans=0; memset(vis,0,sizeof vis);memset(a,0,sizeof a); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); dfs(1,1,0); printf("%d\n",ans); } return 0;}
#include#include #include #define N 1001#define inf 0x3f3f3f3fusing namespace std;int n,m,a,b,ans,cnt;bool vis[N];int k[N],f[N];inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}void dfs(int now,int tot){ if(now==b) {ans=min(ans,tot);return;} if(tot>=ans) return; if(!vis[now]) { vis[now]=1; dfs(now+k[now],tot+1);dfs(now-k[now],tot+1); vis[now]=0; }}int main(){ n=read();a=read();b=read(); for(int i=1;i<=n;i++) k[i]=read(); ans=inf;dfs(a,0); if(ans==inf) printf("-1\n"); else printf("%d\n",ans); return 0;}
#include#include #include #define N 55using namespace std;int n,m,k,ans,cnt,sx,sy;int map[N][N],turn[1201];bool vis[1201][N][N][5];char ch,s[1201][1201];inline int read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}void dfs(int x,int y,int tot,int t)//tot是走了几个方向 ,t是当前方向 { if(vis[tot][x][y][t]) return; vis[tot][x][y][t]=1; if(tot==k+1) { if(turn[k]==2) for(int i=x;i<=n;i++) { if(map[i][y]==1) break;map[i][y]=7;}//7就是标记。 if(turn[k]==1) for(int i=x;i>=1;i--) { if(map[i][y]==1) break;map[i][y]=7;} if(turn[k]==3) for(int i=y;i>=1;i--) { if(map[x][i]==1) break;map[x][i]=7;} if(turn[k]==4) for(int i=y;i<=m;i++) { if(map[x][i]==1) break;map[x][i]=7;} return; } if(t==1) //上 { for(int i=x-1;i>=1;i--) { if(map[i][y]==1) break; dfs(i,y,tot+1,turn[tot+1]); } } if(t==2) //下 { for(int i=x+1;i<=n;i++) { if(map[i][y]==1) break; dfs(i,y,tot+1,turn[tot+1]); } } if(t==3) //左 { for(int i=y-1;i>=1;i--) { if(map[x][i]==1) break; dfs(x,i,tot+1,turn[tot+1]); } } if(t==4) //右 { for(int i=y+1;i<=m;i++) { if(map[x][i]==1) break; dfs(x,i,tot+1,turn[tot+1]); } }}int main(){ n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>ch; if(ch=='X') map[i][j]=1; else map[i][j]=0; if(ch=='*') sx=i,sy=j; } k=read(); for(int i=1;i<=k;i++) scanf("%s",s[i]); for(int i=1;i<=k;i++)//方向 { if(s[i][0]=='N') turn[i]=1; if(s[i][0]=='S') turn[i]=2; if(s[i][0]=='W') turn[i]=3; if(s[i][0]=='E') turn[i]=4; } dfs(sx,sy,1,turn[1]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(map[i][j]==0) cout<<'.'; if(map[i][j]==1) cout<<'X'; if(map[i][j]==7) cout<<'*'; if(j==m) cout<