1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std; //1 :가로 2:세로 3:대각선
#define p pair<int,int>
#define pp pair<p,int>
int n,res=0;
vector<vector<int>> map,visit;
void bfs(int yy,int xx, int ss){
    queue<pp> q;
    q.push(pp(p(yy,xx),ss));
    while(!q.empty()){
        int y= q.front().first.first;
        int x= q.front().first.second;
        int s= q.front().second;
        q.pop();
        if(y==n-1 && x==n-1){
            res++;
            continue;
        }
        if(y+1<n && y+1>=0 &&x+1<n && x+1>=0
           && map[y+1][x]==0 && map[y][x+1]==0 && map[y+1][x+1]==0)
            q.push(pp(p(y+1,x+1),3));
        if(x+1<n && x+1>=0 && s!=2 && map[y][x+1]==0)
            q.push(pp(p(y,x+1),1)); //가로
        if(y+1<n && y+1>=0 && s!=1 && map[y+1][x]==0)
            q.push(pp(p(y+1,x),2)); //세로
    }
    return;
}
int main(){
    cin >> n;
    map.resize(n); visit.resize(n);
    for(int i=0;i<n;i++){
        map[i].resize(n,0); visit[i].resize(n,0);
        for(int j=0;j<n;j++)
            cin >> map[i][j];
    }
    bfs(0,1,1);
    cout << res <<endl;
    
    
    
}