题目
bfs可以搞,但是我还是喜欢dfs,要记忆化不然会T
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const int INF=1<<25;
- int k,n,m,map[25][25],dx[10]={1,-1,0,0},dy[10]={0,0,1,-1},ans;
- int vis[25][25][25];
- bool in(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m; }
- int dfs(int x,int y,int len,int p)
- {
- int ans=INF;
- if(x==n && y==m) return len;
- for(int i=0;i<4;i++)
- {
- int px=x+dx[i],py=y+dy[i];
- // printf("(%d,%d) -> (%d,%d)\n",x,y,px,py);
- int cnt=p;
- if(map[px][py]) cnt++;
- else cnt=0;
- if(in(px,py) && cnt<=k &&(vis[px][py][cnt]<0 || vis[px][py][cnt]>len+1))
- {
- vis[px][py][cnt]=len+1;
- ans=min(ans,dfs(px,py,len+1,cnt));
- }
- }
- return ans;
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- memset(vis,-1,sizeof(vis));
- ans=INF;
- scanf("%d%d%d",&n,&m,&k);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- scanf("%d",&map[i][j]);
- ans=dfs(1,1,0,0);
- if(ans!=INF) printf("%d\n",ans);
- else printf("-1\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2421858.html