반응형
#include <iostream>
using namespace std;
int n, cnt;
int a[5][5];
void DFS(int y, int x)
{
//마지막 위치에 도달하면 경로 개수 1 증가, 종료 조건
if (y == n - 1 && x == n - 1) {
cnt++;
return;
}
//다시 방문하지 않도록 0으로 임시로 바꿈
a[y][x] = 0;
//위쪽으로 방문
if (y > 0 && a[y - 1][x] == 1) DFS(y - 1, x);
//아래쪽으로 방문
if (y < n - 1 && a[y + 1][x] == 1) DFS(y + 1, x);
//왼쪽으로 방문
if (x > 0 && a[y][x - 1] == 1) DFS(y, x - 1);
//오른쪽으로 방문
if (x < n - 1 && a[y][x + 1] == 1) DFS(y, x + 1);
//1로 다시 복원
a[y][x] = 1;
}
int main() {
cin >> n;
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cin >> a[i][j];
}
}
DFS(0, 0);
cout << cnt << endl;
return 0;
}
반응형