【题目链接】：click here~~
【题目大意】：题意：给出一个w*h的方格，问除去不能走的路，从(0,0)到(w,h)共有多少种走法。
【解题思路】：第七场比赛的题，最后一小时在看这道题，比较遗憾最后还是没有A出来，赛后重新看了看题目，理清一下思路，发现就是道简单的dp,
处理一下除去不能走的路，，不过要注意题目的一句话：“The blocking is done in such a way that it isnotpossible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containingonlyWest-to-East and South-to-North walks.”，意思是说：阻塞的街道中分由西向东阻塞或者由南向北阻塞。一旦阻塞，意味着这条路不能通过，但是两边的点还是可以走的，阻塞的街道不影响其他可以走的街道。
因此，总的方案数如何求？用二维dp数组保存全部可以的方案，dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;（注意取模），那么总的方案数ans=dp[w][h],
不能走的方案数：res=dp[x1][y1]*dp[w-x2][h-y2](注意是乘！),最后答案就是（ans-res）%（mod）
代码：
#include <bits/stdc++.h>using namespace std;#define mod 2552int t,w,h,k,x1,y1,x2,y2,ans,num;int dp[1010][1010];int main(){cin>>t;while(t–){cin>>w>>h>>k;int maxx=max(w,h);for(int i=0; i<=maxx; i++) dp[0][i]=dp[i][0]=1;//预处理for(int i=1; i<=w; i++)for(int j=1; j<=h; j++){dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;//总方案数}// cout<<dp[w][h]<<endl;;for(int i=1; i<=k; i++){ans=dp[w][h];cin>>num;for(int i=1; i<=num; i++){cin>>x1>>y1>>x2>>y2;ans-=dp[x1][y1]*dp[w-x2][h-y2];//总方案-阻塞的方案ans=(ans+mod)%mod;}if(ans<0)ans+=mod;printf("%d\n",ans);}}return 0;}
只有经历过地狱般的折磨，才有征服天堂的力量。
