題目鏈接：點擊查看

題目大意：給出一個 n * m 的矩陣，起點及初始方向可以任意選擇，每次可以向前或向右走一步，問有多少種方案可以遍歷所有 n * m 個格子

題目分析：找規(guī)律的題。。但被數(shù)據(jù)范圍誤導了，以為是 dp

手玩一下比較小的樣例不難發(fā)現(xiàn)，每次旋轉(zhuǎn)一定以直走開始，第一次的直走一定從一條邊開始走到相對的另一條邊，否則無論如何也無法遍歷所有格子，而且如果有方案的話，初始的這條邊確定后，答案一定是唯一的

同理將上述所有的有效方案翻轉(zhuǎn)一下方向，這些方案仍然有效，所以答案就是格子之間有多少條直線，然后乘以二，也就是 2 * ( m + n - 2 )，對于 n == 1 和 m == 1 時特判一下就好了

借一下圖：https://martin20150405.github.io/2019/12/17/ccpc-2019-final-ti-jie/

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){int n,m;scanf("%d%d",&n,&m);printf("Case #%d: ",++kase);if(n==1&&m==1)puts("1");else if(n==1||m==1)puts("2");elseprintf("%d\n",2*(n+m-2));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - Spiral Matrix(找规律)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。