<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
Description
晚上，跑男们来了节目的最后一站：江苏省扬州中学，完成最后一项比赛：撕名牌。撕名牌的地点是一个由n\*n房间组成的正方形，每个房间里都有一个数字，表示从这个房间可以通过地道向右或向下穿过几个房间。从左上角开始，如果谁能安全到达右下角就算胜利。
<p><div class='image'><a href='//static.oyohyee.com/post/aoj887.png' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/aoj887.png" /></a></div></p>
<p>这里4*4的方格中每一格表示进入这个房间时，队员可以向右或向下穿过的房间数。<br>
郑恺是奔跑小王子，当他拿到这张地图时，脸都变绿了，速度再快，进了迷宫一样的房间也是没办法啊，还好参加JSOI2015夏令营的小伙伴都在，你能帮帮他算出从左上角可以到达右下角的路径数目吗？</p>
</div><div class="part" title="Input">
第一行为一个整数n，表示棋盘的大小。
以下有n行，每行有n个数字（数字与数字之间有一个空格隔开），表示在相应的格子内，棋子可以向右或向下跳跃的格子数。
</div><div class="part" title="Output">
输出共一行，包含一个数，表示从左上角可以到达右下角的路径数目。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0
</div><div class="output part" title="Sample Output">
3
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p>题意理解如下：<strong>每个方格的数字代表向右/下移动的格数（不能转向）</strong><br>
因此有 <code>f(x,y)=f(x+Map[x][y],y)+f(x,y+Map[x][y])</code><br>
采用记忆化搜索递推即可</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp 又是迷宫 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
/<em>/<br>
#define debug<br>
#include <ctime><br>
//</em>/<br>
#include <cstdio><br>
#include <cstring><br>
#include <iostream><br>
using namespace std;</p>
<p>const int maxn = 105;<br>
int Map[maxn][maxn];<br>
int ans[maxn][maxn];<br>
bool vis[maxn][maxn];</p>
<p>int n;</p>
<p>int dfs(int x, int y) {<br>
if (x &gt; n || y &gt; n)<br>
return 0;</p>
<pre><code>if (ans[x][y] == -1) {
    ans[x][y] = 0;
    if (x + Map [x][y] &lt;= n)
        ans[x][y] += dfs(x + Map [x][y], y);
    if (y + Map [x][y] &lt;= n)
        ans[x][y] += dfs(x, y + Map [x][y]);
}

return ans[x][y];
</code></pre>
<p>}</p>
<p>int main() {<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>while (cin &gt;&gt; n) {
    for (int i = 1; i &lt;= n; i++) {
        for (int j = 1; j &lt;= n; j++) {
            cin &gt;&gt; Map[i][j];
        }
    }
    memset(ans, -1, sizeof(ans));
    ans[n][n] = 1;

    cout &lt;&lt; dfs(1, 1) &lt;&lt; endl;

    // for (int i = 1; i &lt;= n; i++) {
    //     for (int j = 1; j &lt;= n; j++) {
    //         cout &lt;&lt; ans[i][j];
    //     }
    //     cout &lt;&lt; endl;
    // }
}
</code></pre>
<p>#ifdef debug<br>
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);<br>
#endif<br>
return 0;<br>
}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

AOJ 887.又是迷宫