MazeMaker srm 435.5 div2 mid

• 幅優先探索で、行ける所全部に最小到達歩数を記録。
• 到達不可能地点があるかチェック。あるなら、return -1。無い場合、最大の最小到達歩数を返す。
• 障害物で行けない地点は、走査時に除いて考える。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


ostream& operator<<(ostream& ost, const pair<int, int>& p){
  ost << p.first << "\t" << p.second;
  return ost;
}

class MazeMaker{
public:
  vector<vector<int> > minNum;
  int nrow, ncol;
  vector<int> moveRow, moveCol;
  vector<string> maze;
  queue<pair<int, int> > q;

  void printMove(){
    for(int i = 0; i < (int)moveRow.size(); i++){
      cout << "(" << moveRow[i] << ", " << moveCol[i] << ")" << endl;
    }
  }

  void print(){
    for(int i = 0; i < (int)minNum.size(); i++){
      for(int j = 0; j < (int)minNum[i].size(); j++){
	if(maze[i][j] == 'X') cout << "X\t";
	else cout << minNum[i][j] << "\t";
      }
      cout << endl;
    }
    cout << endl;
  }

  void printMaze(){
    for(int i = 0; i < nrow; i++){
      cout << maze[i] << endl;
    }
  }

  int longestPath(vector <string> maze_, int startRow, int startCol, vector <int> moveRow_, vector <int> moveCol_){
    maze = maze_;
    nrow = maze.size();
    ncol = maze[0].size();
    moveRow = moveRow_;
    moveCol = moveCol_;

    printMaze();
    printMove();

    minNum = vector<vector<int> >(nrow, vector<int>(ncol, -1));
    minNum[startRow][startCol] = 0;
    print();

    q = queue<pair<int, int> >();
    q.push(pair<int, int>(startRow, startCol));
    while(q.size() > 0){
      pair<int, int> now = q.front(); q.pop();
      for(int i = 0; i < (int)moveCol.size(); i++){
	int r = now.first + moveRow[i];
	int c = now.second + moveCol[i];	  
	if(check(r, c)){
	  q.push(pair<int, int>(r, c));
	  minNum[r][c] = minNum[now.first][now.second] + 1;
	  print();
	}
      }
    }

    int retmin = 0;
    int retmax = 0;
    for(int i = 0; i < nrow; i++){
      for(int j = 0; j < ncol; j++){
	if(maze[i][j] != 'X'){
	  retmin = min(retmin, minNum[i][j]);
	  retmax = max(retmax, minNum[i][j]);
	}
      }
    }

    return retmin == -1 ? -1 : retmax;
  }

  bool check(int r, int c){
    return
      r < nrow && c < ncol &&
      r >= 0 && c >= 0 &&
      maze[r][c] != 'X' &&
      minNum[r][c] == -1;
  }



};