题意:中文不详述。
思路 :上上上场比赛让一个BFS给虐了,上次比赛让一个三维的给废掉了。。。。。。。所以急于从水题刷起。。。。。。还因为数组开小了WA了5,6次
#include#include #include #include using namespace std;int m,n,sx,sy,ex,ey ;int mapp[17][17] ;int vis[17][17] ;int mpx[400],mpy[400] ;int dire[4][2] = { { 0,-1},{-1,0},{ 0,1},{ 1,0}} ;int flag ;int step ;void DFS(int x,int y){ if(x == ex && y == ey) { flag = 1 ; for(int i = 1 ; i < step ; i++) printf("(%d,%d)->",mpx[i],mpy[i]) ; printf("(%d,%d)\n",ex,ey) ; } else { for(int i = 0 ; i < 4 ; i++) { int xx = x+dire[i][0] ; int yy = y+dire[i][1] ; if(mapp[xx][yy] && xx >= 1 && xx <= m && yy >= 1 && yy <= n && !vis[xx][yy]) { step++ ; vis[xx][yy] = 1 ; mpx[step] = xx ; mpy[step] = yy ; DFS(xx,yy) ; vis[xx][yy] = 0 ; step-- ; } } }}int main(){ while(~scanf("%d %d",&m,&n)) { memset(vis,0,sizeof(vis)) ; memset(mpx,0,sizeof(mpx)) ; memset(mpy,0,sizeof(mpy)) ; for(int i = 1 ; i <= m ; i++) for(int j = 1 ; j <= n ; j++) scanf("%d",&mapp[i][j]) ; scanf("%d %d",&sx,&sy) ; scanf("%d %d",&ex,&ey) ; step = 1 ; mpx[1] = sx ; mpy[1] = sy ; vis[sx][sy] = 1; flag = 0 ; DFS(sx,sy) ; if(!flag) printf("-1\n") ; } return 0;}