#include<iostream> #include<cstdio> #include<cstring> 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 ",ans); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #define N 1001 #define inf 0x3f3f3f3f using 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 "); else printf("%d ",ans); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #define N 55 using 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<<endl; } return 0; }