Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC的不容易啊。。汗。。一个小小的疏忽让我挂了3次~~~把代码贴出来,给后来人指引吧# include <iostream> using namespace std; # include <cstring> class bar { public: int x1,x2,y1,y2; void add(int,int,int,int); bool check(int,int,int,int); }; class graph { private: int map1[100][100]; int map2[100][100]; int endx,endy,w,h; char *path; void peek(int &,int &,int,int,int,int,bool visit[100][100],int map[100][100]); bool check(int,int,int,int,bool visit[100][100]); bool checkbar(int,int,int,int); inline bool barchk(int); inline bool bchk(int,int); inline bool chkd(int,int,int); inline void change(int,int,int&,int&,int&,int&); void culpath(); void buildmap(int,int,int map[100][100]); public: graph(int,int,char*); bool istrue(); }; bar *barrier; int barnum; //-----------------bar start------------------------------------ void bar::add(int x1,int y1,int x2,int y2) { this->x1=x1; this->x2=x2; this->y1=y1; this->y2=y2; } bool bar::check(int x1, int y1, int x2, int y2) { if(x1==this->x1&&x2==this->x2&&y1==this->y1&&y2==this->y2) return 0; else if(x1==this->x2&&x2==this->x1&&y1==this->y2&&y2==this->y1) return 0; else return 1; } //-----------------bar end-------------------------------------- //-----------------graph start---------------------------------- graph::graph(int width,int height,char *temp) { path=temp; w=width; h=height; culpath(); //---------------代价矩阵初始化--------------------- for(int i=0;i<width;i++) for(int j=0;j<height;j++) map1[i][j]=map2[i][j]=9999999; //--------------------------------------------------- } bool graph::checkbar(int x1,int y1,int x2,int y2) { for(int i=1;i<=barnum;i++) if(!barrier[i].check(x1,y1,x2,y2)) return 0; return 1; } bool graph::check(int x1, int y1, int x2, int y2,bool visit[100][100]) { if(x2<0||x2>=w||y2<0||y2>=h) return 0; if(visit[x2][y2]) return 0; for(int i=1;i<=barnum;i++) if(!barrier[i].check(x1,y1,x2,y2)) return 0; return 1; } void graph::culpath() { endx=0; endy=0; for(int i=0;i<strlen(path);i++) switch(path[i]) { case 'U': endy++;break; case 'D': endy--;break; case 'L': endx--;break; case 'R': endx++;break; }; } void graph::buildmap(int x,int y,int map[100][100]) { bool visit[100][100]; memset(visit,0,sizeof(visit)); map[x][y]=0; int xd=x,yd=y,xu=x,yu=y; int count=w*h; while(count>0) { peek(x,y,xd,yd,xu,yu,visit,map); visit[x][y]=1; count--; int len=map[x][y]; if(check(x,y,x+1,y,visit)) { change(x+1,y,xd,yd,xu,yu); if(len+1<map[x+1][y]) map[x+1][y]=len+1; } if(check(x,y,x-1,y,visit)) { change(x-1,y,xd,yd,xu,yu); if(len+1<map[x-1][y]) map[x-1][y]=len+1; } if(check(x,y,x,y-1,visit)) { change(x,y-1,xd,yd,xu,yu); if(len+1<map[x][y-1]) map[x][y-1]=len+1; } if(check(x,y,x,y+1,visit)) { change(x,y+1,xd,yd,xu,yu); if(len+1<map[x][y+1]) map[x][y+1]=len+1; } } } inline void graph::change(int x,int y,int& xd,int &yd,int &xu,int &yu) { if(x<xd) xd=x; if(x>xu) xu=x; if(y<yd) yd=y; if(y>yu) yu=y; } void graph::peek(int &x, int &y, int xd, int yd, int xu, int yu, bool visit[100][100],int map[100][100]) { int min=999999; for(int i=xd;i<=xu;i++) for(int j=yd;j<=yu;j++) if(!visit[i][j]&&map[i][j]<min) { min=map[i][j]; x=i; y=j; } } inline bool graph::bchk(int x,int y) { if(x<0||y<0||x>=w||y>=h) return false; else return true; } inline bool graph::chkd(int x,int y,int n) { int total=0; if(bchk(x-1,y)) if(map1[x-1][y]==n-1&&checkbar(x,y,x-1,y)) total++; if(bchk(x+1,y)) if(map1[x+1][y]==n-1&&checkbar(x,y,x+1,y)) total++; if(bchk(x,y-1)) if(map1[x][y-1]==n-1&&checkbar(x,y,x,y-1)) total++; if(bchk(x,y+1)) if(map1[x][y+1]==n-1&&checkbar(x,y,x,y+1)) total++; if(total==1) return 1; else return 0; } inline bool graph::barchk(int s) { if(map1[barrier[s].x1][barrier[s].y1]+map2[barrier[s].x2][barrier[s].y2]+1>map1[endx][endy]&& map1[barrier[s].x2][barrier[s].y2]+map2[barrier[s].x1][barrier[s].y1]+1>map1[endx][endy]) return 0; return 1; } bool graph::istrue() { buildmap(0,0,map1); buildmap(endx,endy,map2); /* 测试最短路径矩阵 cout<<endl<<endl; for(int j=h-1;j>=0;j--) { for(int i=0;i<w;i++) printf("%5d ",map1[i][j]); cout<<endl; } cout<<endl<<endl; for(int j=h-1;j>=0;j--) { for(int i=0;i<w;i++) printf("%5d ",map2[i][j]); cout<<endl; } */ if(map1[endx][endy]!=strlen(path)) return 0;//最短路径判断 //-------------------------唯一性判断------------------ int tx=0,ty=0; for(int i=0;i<strlen(path);i++) { switch(path[i]) { case 'U': ty++;break; case 'D': ty--;break; case 'L': tx--;break; case 'R': tx++;break; }; if(!chkd(tx,ty,i+1)) return 0; } //----------------------------------------------------- //-----------------------墙多余判断-------------------- for(int i=1;i<=barnum;i++) if(!barchk(i)) return 0; //----------------------------------------------------- return 1;//PASS } //-----------------graph end------------------------------------ int main() { int test; cin>>test; for(int i=1;i<=test;i++) { int w,h; char *temp=new char[10001]; cin>>w>>h; cin>>temp; cin>>barnum; graph data(w,h,temp); barrier=new bar[barnum+1]; for(int j=1;j<=barnum;j++) { int t1,t2,t3,t4; cin>>t1>>t2>>t3>>t4; barrier[j].add(t1,t2,t3,t4); } if(data.istrue()) cout<<"CORRECT"<<endl; else cout<<"INCORRECT"<<endl; delete[] barrier; delete[] temp; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator