AOJ 0193 : Deven-Eleven

問題リンク：Deven-Eleven | Aizu Online Judge

問題概要：
略

使用した言語：C＋＋

解法；
s個の各入力にたいしてbfsでマップ上にお店からの最短コストを保存していく
その後,t個の入力にたいしてbfsで最大のマスをもとめていく
※y軸が偶数か奇数かによってx軸のみる場所をかえなければならない点に注意

mとnの入力を逆にとっていたせいで1時間近く無駄に悩んでしまったのがつらい
問題文はしっかり読んでほしい

コード：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cassert>
#include<vector>
#include<deque>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
int n,m,cnt;
int mincost[110][110];
bool visited[110][110];
int dx[2][6] = {{-1,+0,1,0,-1,-1},{+0,+1,1,1,0,-1}};
int dy[2][6] = {{-1,-1,0,1,+1,+0},{-1,-1,0,1,1,+0}};
 
void dfs(int x,int y)
{
 
  deque<Pi> deq;
  deq.push_back(Pi(P(x,y),0));
  mincost[y][x] = 0;
  visited[y][x] = true;
  cnt = 1;
  while(!deq.empty())
    {
      Pi pi = deq.front(); deq.pop_front();
 
      for(int i=0;i<6;i++)
    {
      int nx = pi.first.first + dx[pi.first.second%2][i];
      int ny = pi.first.second + dy[pi.first.second%2][i];
 
      if(!(0 <= nx && nx < m && 0 <= ny && ny < n))
        continue;
 
      if(mincost[ny][nx] > pi.second + 1)
        {
          if(!visited[ny][nx])
        cnt++;
          visited[ny][nx] = true;
          mincost[ny][nx] = pi.second + 1;
          deq.push_back(Pi(P(nx,ny),pi.second+1));
        }
    }
    }
}
 
int main()
{
  while(cin >> m >> n,m)
    {
      for(int i=0;i<n;i++) 
	for(int j=0;j<m;j++)
	  mincost[i][j] = (1<<29);  
      
      int s,t,mex = 1;
      scanf("%d",&s);
      
      for(int i=0;i<s;i++)
	{
	  int x,y;
	  scanf("%d %d",&x,&y);
	  x--,y--;
	  mincost[y][x] = 0;
	  dfs(x,y);
	}
      
      scanf("%d",&t);
      
      for(int i=0;i<t;i++)
	{   
	  int pre_mincost[n][m];
	  for(int j=0;j<n;j++)
	    for(int k=0;k<m;k++)
	      pre_mincost[j][k] = mincost[j][k],visited[j][k] = false;
	  int p,q;
	  scanf("%d %d",&p,&q);
	  
	  p--,q--;
	  dfs(p,q);
	  
	  mex = max(mex,cnt);
	  for(int j=0;j<n;j++)
	    for(int k=0;k<m;k++)
	      mincost[j][k] = pre_mincost[j][k];
	}
      cout << mex << endl;
    }
  return 0;
}