http://www.ioi-jp.org/joi/2009/2010-yo- ... yo-t5.html
環境はXP,gcc4.6.2です。
#include <iostream>
#include <map>
using namespace std;
struct place{ //座標を格納する構造体
int w; //幅
int h; //高さ
};
bool DiscoveryMap(map<place,int> memo,place element);
//mapに要素が含まれるか調べる
int solve(place now, map<place,int> *memo);
int main()
{
map<place,int> memo;//メモ化再帰用
int w,h;
int answer;
place goal;
cin >> w >> h;
goal.w = w;
goal.h = h;
answer = solve(goal,&memo);
cout << answer;
return 0;
}
int solve(place now, map<place,int> *memo)
{
place next1 , next2;
if( now.w == 1 || now.h == 1 ) //座標が壁際であれば
return 1; //1を返す
if( DiscoveryMap(*memo,now) )//メモの中にあれば
return (*memo)[now]; //その値を返す
next1.w = now.w;
next1.h = now.h - 1; //一個下の座標
next2.w = now.w - 1; //一個左の座標
next2.h = now.h;
(*memo)[now] = solve(next1, memo) + solve(next2, memo);
//メモに答えを格納
return (*memo)[now];
}
bool DIscoveryMap(map<place,int>memo,place element)
{
auto ite = memo.find(element);
return ite != memo.end();
}
g++ --std=c++0x 09-5.cpp
In file included from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/string:50:0,
from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/locale_classes.h:42,
from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/ios_base.h:43,
from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/ios:43,
from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/ostream:40,
from j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/iostream:40,
from 09-5.cpp:1:
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_function.h: メンバ関数 'bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = place]' 内:
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_map.h:452:2: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = place, _Tp = int, _Compare = std::less<place>, _Alloc = std::allocator<std::pair<const place, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int, std::map<_Key, _Tp, _Compare, _Alloc>::key_type = place]' から実体化されました
09-5.cpp:40:13: instantiated from here
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_function.h:236:22: エラー: 'operator<' で '__x < __y' 内にあるものが適合しません
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_function.h:236:22: 備考: 候補:
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_pair.h:207:5: 備考: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_iterator.h:291:5: 備考: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_iterator.h:341:5: 備考: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_IteratorL>&, const std::reverse_iterator<_IteratorR>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_iterator.h:1049:5: 備考: template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_iterator.h:1055:5: 備考: template<class _Iterator> bool std::operator<(const std::move_iterator<_Iterator>&, const std::move_iterator<_Iterator>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/basic_string.h:2510:5: 備考: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/basic_string.h:2522:5: 備考: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/basic_string.h:2534:5: 備考: template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::basic_string<_CharT, _Traits, _Alloc>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_tree.h:856:5: 備考: template<class _Key, class _Val, class _KeyOfValue, class _Compare, class _Alloc> bool std::operator<(const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&, const std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_map.h:894:5: 備考: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::map<_Key, _Tp, _Compare, _Alloc>&, const std::map<_Key, _Tp, _Compare, _Alloc>&)
j:\mingw\bin\../lib/gcc/mingw32/4.6.2/include/c++/bits/stl_multimap.h:812:5: 備考: template<class _Key, class _Tp, class _Compare, class _Alloc> bool std::operator<(const std::multimap<_Key, _Tp, _Compare, _Alloc>&, const std::multimap<_Key, _Tp, _Compare, _Alloc>&)