#pragma region include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #include #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)1e18; const double PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; vector< vector > Gra; vector dist; void solve(){ int W,H,N; cin >> W >> H >> N; Gra = vector< vector >(W*H); vector< vector > RR(W,vector(H+1,0)); vector< vector > CC(H,vector(W+1,0)); for(int i=0;i> M; ++M; vector B(M); for(int j=0;j> B[j]; } for(int j=1;j v ){ swap(u,v); } if( u%W == v%W ){//縦移動RR int rank = u%W; RR[rank][u/W]++; RR[rank][(v/W)]--; /*for(int k=u+W;k<=v;k+=W){ Gra[k-W].push_back(k); Gra[k].push_back(k-W); }*/ }else{//横移動CC int rank = u/W; CC[rank][u%W]++; CC[rank][(v%W)]--; /*for(int k=u+1;k<=v;++k){ Gra[k-1].push_back(k); Gra[k].push_back(k-1); }*/ } } } for(int c=0;c 0 ){ Gra[0*W+c].push_back(1*W+c); Gra[1*W+c].push_back(0*W+c); } for(int r=1;r 0 ){ Gra[r*W+c].push_back((r+1)*W+c); Gra[(r+1)*W+c].push_back(r*W+c); } } } for(int r=0;r 0 ){ Gra[r*W+0].push_back(r*W+1); Gra[r*W+1].push_back(r*W+0); } for(int c=1;c 0 ){ Gra[r*W+c].push_back(r*W+c+1); Gra[r*W+c+1].push_back(r*W+c); } } } dist = vector(W*H,INF); vector visit(W*H, false); queue que; que.push(0);//スタート地点 visit[0] = true; dist[0] = 0; while(!que.empty()){ int now = que.front();que.pop(); int size = Gra[now].size(); for(int i=0;i