#include<iostream>
#include<iomanip>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e2 + 10;
int q[N][N];
int q1[N][N];
int h, w;
int dxy[4][2] = { {0,-1},{0,1},{-1,0},{+1,0} };
int cnt;
map<int, int> st;
void dfs(int x,int y) {
if (y == h && x == w) {
cnt++;
return;
};
for (int i = 0; i < 4; i++) {
int k1 = x, k2 = y;
int dx = x + dxy[i][0], dy = y + dxy[i][1];
if (dy < 1 || dx < 1 || dx > w || dy > h || st.count(q[dx][dy]) > 0|| q1[dx][dy]>0) continue;
q1[dx][dy]++;
st[q[dx][dy]]++;
//cout << q[dx][dy] << ' ';
dfs(dx, dy);
st.erase(q[dx][dy]);
q1[dx][dy] --;
dx = k1, dy = k2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> h >> w;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
cin >> q[i][j];
st[q[1][1]]++;
q1[1][1]++;
dfs(1, 1);
cout << cnt;
return 0;
}
失败品2
作者：
Soel
,
2023-03-11 21:27:58
,
所有人可见
,
阅读 184
Soel
,
2023-03-11 21:27:58
,
所有人可见
,
阅读 184
2 评论
x
#include<iostream> #include<iomanip> #include<cstring> #include<queue> #include<cmath> #include<vector> #include<map> #include<set> using namespace std; typedef pair<int, int> PII; const int N = 1e2 + 10; int q[N][N]; int q1[N][N]; int h, w; int dxy[3][2] = { {0,1},{1,0}}; long long cnt; //map<int, int> st; set<int> st; void dfs(int y,int x) { if (y == h && x == w) { cnt++; return; }; for (int i = 0; i < 2; i++) { int dx = x + dxy[i][0], dy = y + dxy[i][1]; if (dx > w || dy > h || st.count(q[dy][dx])||q[dy][dx]==0) continue; //q1[dx][dy]++; st.insert(q[dy][dx]); //cout << dy << ' '<<dx<<' '; //cout << endl; dfs(dy, dx); st.erase(q[dy][dx]); //q1[dx][dy] --; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> h >> w; for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> q[i][j]; st.insert(q[1][1]); //q1[1][1]++; dfs(1, 1); cout << cnt; return 0; }剪枝
https://atcoder.jp/contests/abc293/tasks/abc293_c