SRM453.5 Div1 Easy(250) MazeMaker
1日勘違いしてて、参加し損ねた。ぐぬぬ。
#include <vector> #include <string> using namespace std; class MazeMaker { public: int longestPath( vector<string> maze, int startRow, int startCol, vector<int> moveRow, vector<int> moveCol ); }; int MazeMaker::longestPath( vector<string> maze, int startRow, int startCol, vector<int> moveRow, vector<int> moveCol ) { int w = (int)maze[0].size(); int h = (int)maze.size(); vector<vector<int> > step( h, vector<int>( w, INT_MAX ) ); step[startRow][startCol] = 0; for ( int s=0; ; s++ ) { bool update = false; for ( int y=0; y<h; y++ ) for ( int x=0; x<w; x++ ) if ( step[y][x] == s ) { for ( int i=0; i<(int)moveRow.size(); i++ ) { int tx = x + moveCol[i]; int ty = y + moveRow[i]; if ( 0 <= tx && tx < w && 0 <= ty && ty < h && maze[ty][tx] == '.' && step[ty][tx] == INT_MAX ) { step[ty][tx] = s + 1; update = true; } } } if ( ! update ) break; } int answer = 0; for ( int y=0; y<h; y++ ) for ( int x=0; x<w; x++ ) if ( maze[y][x] == '.' ) answer = max( answer, step[y][x] ); return answer==INT_MAX ? -1 : answer; }