PKU 1101 The Game
http://poj.org/problem?id=1101
ボードの上にいくつかのゲームピースが並べられている。
ある地点のゲームピースからある地点のゲームピースまで何本の折れ線で結べるかを答えるというような問題。
ただし、折れ線はボードの外に出ても良いものとし、出発地点のピースと到着地点のピース以外とは交差しないようにする。
'X'を'#'を勘違いしてしばらく詰まるというアホっぷりを発揮した。
それとそれぞれのボードごとに改行するというのを読み落としたPEで1WA
string in[100]; bool vis[100][100]; main(){ int w,h,b=0; while(cin>>w>>h,w|h){ printf("Board #%d:\n",++b); getchar(); in[0]=in[h+1]=string(w+2,' '); rep(i,h){ getline(cin,in[i+1]); in[i+1]=' '+in[i+1]+' '; } h+=2; w+=2; int x1,y1,x2,y2; int pa=0; while(cin>>x1>>y1>>x2>>y2,x1){ swap(x1,y1),swap(x2,y2); memset(vis,0,sizeof(vis)); priority_queue<pair<int,PI> > q; q.push(mp(0,mp(x1,y1))); int ans=-1; while(!q.empty()){ int cc=-q.top().F,cx=q.top().S.F,cy=q.top().S.S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; if(cx==x2 && cy==y2){ ans=cc; break; } if((cx!=x1 || cy!=y1) && in[cx][cy]=='X')continue; rep(i,4){ for(int j=1;;j++){ int nx=cx+dx[i]*j,ny=cy+dy[i]*j; if(nx<0 || h<=nx || ny<0 || w<=ny || vis[nx][ny])break; q.push(mp(-cc-1,mp(nx,ny))); if(in[nx][ny]=='X')break; } } } if(ans!=-1)printf("Pair %d: %d segments.\n",++pa,ans); else printf("Pair %d: impossible.\n",++pa); } puts(""); } }