原题：飞越原野
很简单的一道DFS题，注意看好题意就行了
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char map[110][110]; int v[110][110]; int n,m,d; int X[]= {0,0,1,-1}; int Y[]= {1,-1,0,0}; int yes,sum; int judge(int x,int y) { if(x<0||x>=m||y<0||y>=n) return 0; return 1; } void dfs(int x,int y,int t,int value) { // printf("%d %d %d\n",x,y,t); // getchar(); if(x==m-1&&y==n-1){ yes=1; sum=min(sum,t); return ; } for(int i=0; i<4; i++) { int xx=x+X[i]; int yy=y+Y[i]; if(!judge(xx,yy)||v[xx][yy])continue ; int k=0; if(map[xx][yy]=='L') { if(!value) continue ; while(judge(xx,yy)&&map[xx][yy]=='L'){ xx=xx+X[i]; yy=yy+Y[i]; k++; } k++; if(!judge(xx,yy)||map[xx][yy]!='P'||v[xx][yy]||k>value) continue ; } v[xx][yy]=1; dfs(xx,yy,t+1,value-k); v[xx][yy]=0; } } int main() { int i; while(~scanf("%d %d %d",&m,&n,&d)) { memset(map,0,sizeof(map)); for(i=0; i<m; i++) scanf("%s",map[i]); memset(v,0,sizeof(v)); yes=0; sum=99999999; v[0][0]=1; dfs(0,0,0,d); printf("%d\n",sum); } return 0; }
