AOJ:1144 Curling 2.0
盤面ごとキューに入れて無理やりBFSで解きました。
正直BFSで解くべきではありませんでした。
#define _USE_MATH_DEFINES #define INF 100000000 #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #include <bitset> #include <list> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef pair <int,int> P; static const double EPS = 1e-8; char stage[20][20]; int tx[] = {-1,0,1,0}; int ty[] = {0,1,0,-1}; class Data{ public: char dx; char dy; char stage[20][20]; Data(char dx,char dy,char stage[20][20]){ this->dx = dx; this->dy = dy; memcpy(this->stage,stage,sizeof(char)*(20*20)); } }; typedef pair <int,Data> PP; int main(){ int w,h; char sx,sy,gx,gy; while(~scanf("%d %d",&w,&h)){ if(w==h && h==0) break; for(int y=0;y<h;y++){ for(int x=0;x<w;x++){ int n; scanf("%d",&n); stage[y][x] = n; if(stage[y][x]==2){ sx=x; sy=y; } else if(stage[y][x]==3){ gx=x; gy=y; } } } queue<PP> que; que.push(PP(0,Data(sx,sy,stage))); int res = 11; while(!que.empty()){ int c = que.front().first; int qx = que.front().second.dx; int qy = que.front().second.dy; char tmpStage[20][20]; memcpy(tmpStage,que.front().second.stage,sizeof(char)*(20*20)); que.pop(); for(int i=0;i<4;i++){ for(int d=1;d<=max(w,h);d++){ int dx = qx + tx[i]*d; int dy = qy + ty[i]*d; if(dx < 0 || dx >= w || dy < 0 || dy >= h) break; if(d==1 && tmpStage[dy][dx] == 1) break; if(tmpStage[dy][dx] == 1){ char mx = dx - tx[i]; char my = dy - ty[i]; if(c+1 <= 10){ //cost[my][mx] = c+1; tmpStage[dy][dx] = 0; que.push(PP(c+1,Data(mx,my,tmpStage))); //cout << mx << " " << my << endl; tmpStage[dy][dx] = 1; } break; } else if(tmpStage[dy][dx] == 3){ if(c+1 <= 10){ res = min(res,c+1); } break; } } } } printf("%d\n", res > 10 ? -1 : res); } }