yukicoder : No.367 ナイトの転身
問題URL:http://yukicoder.me/problems/no/367
問題レベル:★★★
問題
H行W列のチェス盤上で、ミニビショップとナイトを移動させる。
ミニビショップは斜めに移動できる。
ナイトからスタートでRの場所にくるとナイトはミニビショップになり、ミニビショップはナイトになる。
スタート地点のマスからゴール地点のマスまでの最短手数を出力する。
ゴールできない場合は-1を出力する。
解法
BFSで解ける。
ただし、駒が2種類あるので3次元配列を使ってナイト用、ミニビショップ用の盤の配列を用意する必要がある。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <queue> using namespace std; using ull = unsigned long long; using ll = long long; using lli = long long int; using ld = long double; using pa = pair<int,int>; using ppa = pair<pa,int>; #define SORT(v, n) sort(v, v+n); #define ALL(v) v.begin(),v.end() #define VSORT(v) sort(ALL(v)) #define GRESORT(v) sort(ALL(v),greater<ll>()) #define REVERSE(v) reverse(ALL(v)) #define overlap(v) v.erase(unique(ALL(v)),v.end()) #define debug(x) cout << #x << ": " << x << endl #define FOR(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i = (b-1); i >= a; i--) #define rrep(i,n) RFOR(i,0,n) #define INF 999999999 #define mins(a,b) a = min(a,b) #define maxs(a,b) a = max(a,b) //4近傍 //int dy[]={0, 1, 0, -1}; //int dx[]={1, 0, -1, 0}; //8近傍 //int dy[]={0,0,1,-1,1,1,-1,-1}; //int dx[]={1,-1,0,0,1,-1,1,-1}; //knight int kdy[] = {-2,-2,-1,-1,1,1,2,2}; int kdx[] = {-1,1,-2,2,-2,2,-1,1}; //bishop int bdy[] = {1,1,-1,-1}; int bdx[] = {1,-1,1,-1}; ll mod = 1000000007; bool check(int x, int y, int h, int w){ return (x < 0 || y < 0 || y >= h || x >= w); } void solve() { int h,w; cin >> h >> w; char c[510][510]; int sx,sy,gx,gy; int d[510][510][2] = {}; rep(i,h){ rep(j,w){ cin >> c[i][j]; if(c[i][j] == 'S'){ sy = i; sx = j; } if(c[i][j] == 'G'){ gy = i; gx = j; } d[i][j][0] = INF; d[i][j][1] = INF; } } d[sy][sx][0] = 0; queue<ppa> q; q.push(ppa(pa(sx,sy),0)); while(!q.empty()) { ppa p = q.front(); q.pop(); pa pp = p.first; int x = pp.first, y = pp.second, r = p.second; if (gx == x && gy == y) break; int val = r == 0 ? 8 : 4; auto dy = r == 0 ? kdy : bdy; auto dx = r == 0 ? kdx : bdx; rep(i, val) { int xx = x + dx[i]; int yy = y + dy[i]; if (check(xx, yy, h, w)) continue; int nr = r; if(c[yy][xx] == 'R') nr ^= 1; if (d[yy][xx][nr] == INF) { d[yy][xx][nr] = d[y][x][r] + 1; q.push(ppa(pa(xx, yy), nr)); } } } cout << (d[gy][gx][0] != INF || d[gy][gx][1] != INF ? min(d[gy][gx][0],d[gy][gx][1]) : -1) << endl; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); solve(); return 0; }
謎
以下のソースコード書いたが、なぜかWAを食らった。
理由がわからないので誰か教えてください。
Rのマスに到達すると
if(c[yy][xx] == 'R') r = (r+1) % 2;
として駒を切り替えていたが、なぜかうまく動作しなかった。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <queue> using namespace std; using ull = unsigned long long; using ll = long long; using lli = long long int; using ld = long double; using pa = pair<int,int>; using ppa = pair<pa,int>; #define SORT(v, n) sort(v, v+n); #define ALL(v) v.begin(),v.end() #define VSORT(v) sort(ALL(v)) #define GRESORT(v) sort(ALL(v),greater<ll>()) #define REVERSE(v) reverse(ALL(v)) #define overlap(v) v.erase(unique(ALL(v)),v.end()) #define debug(x) cout << #x << ": " << x << endl #define FOR(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i = (b-1); i >= a; i--) #define rrep(i,n) RFOR(i,0,n) #define INF 999999999 #define mins(a,b) a = min(a,b) #define maxs(a,b) a = max(a,b) //4近傍 //int dy[]={0, 1, 0, -1}; //int dx[]={1, 0, -1, 0}; //8近傍 //int dy[]={0,0,1,-1,1,1,-1,-1}; //int dx[]={1,-1,0,0,1,-1,1,-1}; //knight int kdy[] = {-2,-2,-1,-1,1,1,2,2}; int kdx[] = {-1,1,-2,2,-2,2,-1,1}; //bishop int bdy[] = {1,1,-1,-1}; int bdx[] = {1,-1,1,-1}; ll mod = 1000000007; bool check(int x, int y, int h, int w){ return (x < 0 || y < 0 || y >= h || x >= w); } void solve() { int h,w; cin >> h >> w; char c[510][510]; int sx,sy,gx,gy; int d[510][510][2] = {}; rep(i,h){ rep(j,w){ cin >> c[i][j]; if(c[i][j] == 'S'){ sy = i; sx = j; } if(c[i][j] == 'G'){ gy = i; gx = j; } d[i][j][0] = INF; d[i][j][1] = INF; } } d[sy][sx][0] = 0; queue<ppa> q; q.push(ppa(pa(sx,sy),0)); while(!q.empty()){ ppa p = q.front(); q.pop(); pa pp = p.first; int x = pp.first, y = pp.second, r = p.second; //debug(x); debug(y); debug(r); if(gx == x && gy == y) break; if(r == 0){ rep(i,8){ int xx = x + kdx[i]; int yy = y + kdy[i]; if(check(xx,yy,h,w)) continue; if(c[yy][xx] == 'R') r = (r+1) % 2; if(d[yy][xx][0] == INF){ d[yy][xx][r] = d[y][x][0] + 1; q.push(ppa(pa(xx,yy),r)); } } }else{ rep(i,4){ int xx = x + bdx[i]; int yy = y + bdy[i]; if(check(xx,yy,h,w)) continue; if(c[yy][xx] == 'R') r = (r+1) % 2; if(d[yy][xx][1] == INF){ d[yy][xx][r] = d[y][x][1] + 1; q.push(ppa(pa(xx,yy),r)); } } } } cout << (d[gy][gx][0] != INF || d[gy][gx][1] != INF ? min(d[gy][gx][0],d[gy][gx][1]) : -1) << endl; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); solve(); return 0; }
謎解決
rをifで分岐した後にrの変数の値が0になったり1になったりして分岐した意味がなくなり配列にちゃんと格納されていなかっただけ。
まとめ
まだまだだね。