Staircase Walk: 走格子 (Stack)

0

1

2

3


4

5

6

7


8

9

10

11


n rows, m colums 

3 rows, 4 columns

/*
Staircase Walk: 走格子的版本, n rows, m columns
相當於 http://mathworld.wolfram.com/StaircaseWalk.html
n=n+1, m=m+1
*/

#include<iostream>
#include<stack>
using namespace std;
int main()
{   
 int n,m,count=0;
 stack<int> s;
 cin >> n >> m;
 s.push(0);
 while(!s.empty()){
  int c = s.top();s.pop();
  if (c==(n*m-1)){
   count++;
  }
  else{
   if ((c+1)%m!=0) s.push(c+1);   
   if ((c+m)<n*m) s.push(c+m);  
  }
 }
 cout << count;
 system("pause");
 return 0;
}