ICPC練習会2011 Problem.B ブレイブ・フォース・ストーリー
nステップ六角形のマスを移動できるとき、移動可能なマスはいくつあるか数える問題。
障害物があるのでただ数えるだけではダメ。
深さ優先でもいけるよね・・・と思ってやったら、複雑なことになってしまった。マスが正方形ならそれでいいんだけど、この問題ではダメでした。
以下のソースは幅優先で書きなおしてみたもの。
#include <iostream> #include <queue> #include <map> #include <algorithm> using namespace std; const int MAX = 100; typedef pair<int, int> pii; char flag[MAX*2][MAX*2]; int main() { while(true) { int t, n; cin >> t >> n; if(t==0&&n==0) break; fill(flag[0], flag[MAX*2-1]+MAX*2,0); for(int i=0;i<n;i++) { int x, y; cin >> x >> y; flag[y+MAX][x+MAX] = 1; } int sx, sy; cin >> sx >> sy; queue<pair<pii,int> > q; q.push(make_pair(pii(sx, sy),0)); int count = 0; while(!q.empty()) { pair<pii,int> p = q.front(); pii a = p.first; int step = p.second; q.pop(); if(flag[a.second+MAX][a.first+MAX]) continue; flag[a.second+MAX][a.first+MAX] = 1; count++; if(step<t) { q.push(make_pair(pii(a.first+1, a.second), step+1)); q.push(make_pair(pii(a.first-1, a.second), step+1)); q.push(make_pair(pii(a.first, a.second+1), step+1)); q.push(make_pair(pii(a.first, a.second-1), step+1)); q.push(make_pair(pii(a.first+1, a.second+1), step+1)); q.push(make_pair(pii(a.first-1, a.second-1), step+1)); } } cout << count << endl; } return 0; }