8号唱片上传系统,俏皮公主闯校园,金蛇醉心
这题可以使用递归来进行求解,让点分别向4个方向进行探索,直到遇到目标点,或者最后执行失败。如果找到了目标顶点,就对totalStep进行对比赋值。但step已经比目前的totalStep大时,应忽略这种情况,因为这样下去是没有意义的。
题目如下:
5 4 XXXXX X X XXX X XXX 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0 0 0
Board #1: Pair 1: 4 segments. Pair 2: 3 segments. Pair 3: impossible.
#include <bits/stdc++.h> using namespace std; int w,h; char s[100][100]; bool mark[100][100]; int direction[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; int totalStep=100000; void findTotalPath(int x1,int y1,int x2,int y2,int direct,int step){ //cout<<x1<<" "<<y1<<","<<x2<<" "<<y2<<endl; if(step>totalStep) return; if(x1==x2&&y1==y2){ if(step<totalStep){ totalStep=step; } return; } for(int i=0;i<4;i++){ /*if((direct==0&&i==2)||(direct==1&&i==3)||(direct==2&&i==0)||(direct==3&&i==1)) continue;*/ int yy1=y1+direction[i][0]; int xx1=x1+direction[i][1]; //if((xx1<0)||(yy1<0)||(xx1>=h+2)||(yy1>=w+2)||(mark[yy1][xx1]==true)||((s[yy1][xx1]=='X')&&(yy1!=y2||xx1!=x2))) continue; /*cout<<x1<<" -"<<y1<<endl; cout<<xx1<<" "<<yy1<<endl;*/ if((xx1>-1)&&(xx1<w+2)&&(yy1>-1)&&(yy1<h+2)&&(((s[yy1][xx1]==' ')&&(mark[yy1][xx1]==false))||((xx1==x2)&&(yy1==y2)&&(s[yy1][xx1]=='X')))){ //if ((xx1 > -1) && (xx1< w + 2) && (yy1> -1) && (yy1 < h + 2)&& (((s[y][x] == ' ') && (mark[y][x] == false))||((xx1==x2)&& (yy1==y2) && (s[y][x] == ‘X’)))){ mark[yy1][xx1]=true; if(direct!=i){ findTotalPath(xx1,yy1,x2,y2,i,step+1); }else{ findTotalPath(xx1,yy1,x2,y2,i,step); } mark[yy1][xx1]=false; } } } int main(){ int id=1; while(1){ /*cin>>w>>h; cin.ignore();*/ scanf("%d %d",&w,&h); if(w==0&&h==0) break; /*for(int i=0;i<h+2;i++){ s[i][0]=s[i][w+1]=' '; } for(int j=0;j<w+2;j++){ s[0][j]=s[w+1][j]=' '; }*/ for (int i = 0; i <100; i ++) s[0][i] =s[i][0] = ' '; for(int i=1;i<h+1;i++){ getchar(); //string str=""; //getline(cin,str); for(int j=1;j<w+1;j++){ //s[i][j]=str[j-1]; s[i][j]=getchar(); } } for (int i = 0; i <= w; i ++) s[h + 1][i + 1] = ' '; for (int i = 0; i <= h; i ++) s[i + 1][w + 1] = ' '; cout<<"Board #"<<id<<":"<<endl; id++; int x1,y1,x2,y2; int subId=0; while(1){ subId++; totalStep=100000; memset(mark, false, sizeof(mark)); cin>>x1>>y1>>x2>>y2; if(x1==0&&y1==0&&x2==0&&y2==0) break; int step=0; int direct=-1; findTotalPath(x1,y1,x2,y2,direct,step); if(totalStep<100000) cout<<"Pair "<<subId<<": "<<totalStep<<" segments."<<endl; else{ cout<<"Pair "<<subId<<": "<<"impossible."<<endl; } } cout<<endl; } }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论