#include <iostream>using namespace std;#define inf 0x3fffffff#define M 105//1、wan用于转弯数剪枝；2、step用于步数剪枝，就不用vis标记访问了int r, c, ex, ey, k, wan[M][M];char mapp[M][M];int x_move[4] = {-1, 0, 1, 0};int y_move[4] = {0, 1, 0, -1};bool flag;int times=0;/*void showmap(int x,int y)//用这个可以打印出来研究{ int i,j; printf("**************%d****************\n",times); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) printf("%c",i==x&j==y?'@':mapp[i][j]); printf("\n"); } printf("当前位置x=%d,y=%d\n",x+1,y+1); for (i = 0; i < r; i++) { for (j = 0; j < c; j++) if(wan[i][j]==inf) printf("N"); else printf("%d",wan[i][j]); printf("\n"); } times++;} */void dfs (int x, int y, int dir) //dir为当前方向{ if (x == ex && y == ey) { if (wan[x][y] <= k) flag = true; return ; } //x !=ex && y != ey 说明必须至少再转一次弯，但是已经不能再转了 if (x !=ex && y != ey && wan[x][y] == k) return ; if (wan[x][y] > k) //转弯数超过k不用往下走了 return ; for (int i = 0; i < 4; i++) { int tx = x + x_move[i]; int ty = y + y_move[i]; // showmap(tx,ty); if (tx < 0 || tx >= r || ty < 0 || ty >= c) continue; //转弯数相等不可剪掉，所以是wan[tx][ty] < wan[x][y]而不是wan[tx][ty] <= wan[x][y] if (mapp[tx][ty] == '*' || wan[tx][ty] < wan[x][y]) continue; if (dir != -1 && i != dir && wan[tx][ty] < wan[x][y] + 1) /*如果下一步不是初始位置而且下一步要转弯而且下一步的转弯数还更小那就不走这步，同时避免了走回头路*/ continue; wan[tx][ty] = wan[x][y]; if (dir != -1 && i != dir) wan[tx][ty]++; //如果方向变了转弯+1 dfs (tx, ty, i); if (flag) return ; }}
int main(){//freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);//freopen("C:\\Users\\Sky\\Desktop\\1.out","w",stdout); int t, i, j, sx, sy; //sx， sy是起点 scanf ("%d", &t); while (t--) { scanf ("%d%d", &r, &c); for (i = 0; i < r; i++) scanf ("%s", mapp[i]); scanf ("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex); sx--, sy--, ex--, ey--; //我从0开始编号，而题目是从1开始 for (i = 0; i < r; i++) for (j = 0; j < c; j++) wan[i][j] = inf; //初始化转弯数和步数为无穷大 wan[sx][sy] = 0; //到达起点的转弯数 flag = false; dfs (sx, sy, -1); //一开始可以走任意方向，所以设方向为-1 if (flag) puts ("yes"); else puts ("no"); } return 0;}
打印结果
**************0****************...***.**...........*....当前位置x=0,y=10NNNNNNNNNNNNNNNNNNNNNNNN**************1****************.@.***.**...........*....当前位置x=1,y=20NNNNNNNNNNNNNNNNNNNNNNNN**************2****************...***.**...........*....当前位置x=0,y=200NNNNNNNNNNNNNNNNNNNNNNN**************3****************..@***.**...........*....当前位置x=1,y=300NNNNNNNNNNNNNNNNNNNNNNN**************4****************...***.**...........*....当前位置x=0,y=3000NNNNNNNNNNNNNNNNNNNNNN**************5****************...@**.**...........*....当前位置x=1,y=4000NNNNNNNNNNNNNNNNNNNNNN**************6****************...***.@*...........*....当前位置x=2,y=3000NNNNNNNNNNNNNNNNNNNNNN**************7****************.@.***.**...........*....当前位置x=1,y=2000NNNNNNNNNNNNNNNNNNNNNN**************8****************...***@**...........*....当前位置x=2,y=2000NNNNNNNNNNNNNNNNNNNNNN**************9****************@..***.**...........*....当前位置x=1,y=1000NNN1NNNNNNNNNNNNNNNNNN**************10****************...**@.**...........*....当前位置x=2,y=1000NNN1NNNNNNNNNNNNNNNNNN**************11****************...***.**...........*....当前位置x=1,y=0000NNN1NNNNNNNNNNNNNNNNNNno**************12****************...***.**...........*....当前位置x=0,y=10NNNNNNNNNNNNNNNNNNNNNNNN**************13****************.@.***.**...........*....当前位置x=1,y=20NNNNNNNNNNNNNNNNNNNNNNNN**************14****************...***.**...........*....当前位置x=0,y=200NNNNNNNNNNNNNNNNNNNNNNN**************15****************..@***.**...........*....当前位置x=1,y=300NNNNNNNNNNNNNNNNNNNNNNN**************16****************...***.**...........*....当前位置x=0,y=3000NNNNNNNNNNNNNNNNNNNNNN**************17****************...@**.**...........*....当前位置x=1,y=4000NNNNNNNNNNNNNNNNNNNNNN**************18****************...***.@*...........*....当前位置x=2,y=3000NNNNNNNNNNNNNNNNNNNNNN**************19****************.@.***.**...........*....当前位置x=1,y=2000NNNNNNNNNNNNNNNNNNNNNN**************20****************...***@**...........*....当前位置x=2,y=2000NNNNNNNNNNNNNNNNNNNNNN**************21****************.@.***.**...........*....当前位置x=1,y=2000NNN1NNNNNNNNNNNNNNNNNN**************22****************...***.@*...........*....当前位置x=2,y=3000NNN1NNNNNNNNNNNNNNNNNN**************23****************...***.**..@........*....当前位置x=3,y=2000NNN1NNNNNNNNNNNNNNNNNN**************24****************...***@**...........*....当前位置x=2,y=2000NNN1NNNN1NNNNNNNNNNNNN**************25****************...***.**...@.......*....当前位置x=3,y=3000NNN1NNNN1NNNNNNNNNNNNN**************26****************...***.@*...........*....当前位置x=2,y=3000NNN1NNNN12NNNNNNNNNNNN**************27****************...***.**....@......*....当前位置x=3,y=4000NNN1NNNN12NNNNNNNNNNNN**************28****************...***.*@...........*....当前位置x=2,y=4000NNN1NNNN122NNNNNNNNNNN**************29****************...***.**.....@.....*....当前位置x=3,y=5000NNN1NNNN122NNNNNNNNNNN**************30****************...***.**@..........*....当前位置x=2,y=5000NNN1NNNN1222NNNNNNNNNN**************31****************...***.**...........*....当前位置x=3,y=6000NNN1NN3N1222NNNNNNNNNN**************32****************...***.**..........@*....当前位置x=4,y=5000NNN1NN3N1222NNNNNNNNNN**************33****************...***.**....@......*....当前位置x=3,y=4000NNN1NN3N1222NNNN3NNNNN**************34****************...***.**.........@.*....当前位置x=4,y=4000NNN1NN3N1222NNNN3NNNNN**************35****************...***.**...@.......*....当前位置x=3,y=3000NNN1NN3N1222NNN33NNNNN**************36****************...***.**........@..*....当前位置x=4,y=3000NNN1NN3N1222NNN33NNNNN**************37****************...***.**..@........*....当前位置x=3,y=2000NNN1NN3N1222NN333NNNNN**************38****************...***.**.......@...*....当前位置x=4,y=2000NNN1NN3N1222NN333NNNNN**************39****************...***.**..@........*....当前位置x=3,y=2000NNN1NN3N1222N1333NNNNN**************40****************...***.**........@..*....当前位置x=4,y=3000NNN1NN3N1222N1333NNNNN**************41****************...***.**...........*@...当前位置x=5,y=2000NNN1NN3N1222N1233NNNNN**************42****************...***.**.......@...*....当前位置x=4,y=2000NNN1NN3N1222N1233N1NNN**************43****************...***.**...........*.@..当前位置x=5,y=3000NNN1NN3N1222N1233N1NNN**************44****************...***.**...........*....当前位置x=6,y=2000NNN1NN3N1222N1233N12NN**************45****************...***.**...........@....当前位置x=5,y=1000NNN1NN3N1222N1233N12NN**************46****************...***.**......@....*....当前位置x=4,y=1000NNN1NN3N1222N1233N12NN**************47****************...***.**.@.........*....当前位置x=3,y=1000NNN1NN3N122221233N12NN**************48****************...***.**.......@...*....当前位置x=4,y=2000NNN1NN33122221233N12NN**************49****************...***.**...........@....当前位置x=5,y=1000NNN1NN33122221233N12NN**************50****************...***.**...........*....当前位置x=4,y=0000NNN1NN33122221233N12NN**************51****************...***.**.@.........*....当前位置x=3,y=1000NNN1NN33122221233N12NNyes
转载于:https://www.cnblogs.com/Skyxj/p/3182818.html
