|
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; int board[17][301]; int now[301]; bool check(int n){ for (int i = 1; i <= n; i++) { if (now[i] != 1) { return false; } } return true; } bool legal(int n){ for (int i = 1; i <= n; i++) { if (now[i] > 1) { return false; } } return true; } bool dfs(int m,int n,int cur){ if (check(n)) { return true; } if (cur > m) { return false; } for (int i = 1;i <= n; i++) { now[i] += board[cur][i]; } if (legal(n)) { if (dfs(m, n, cur+1)) { return true; } } for (int i = 1; i <= n; i++) { now[i] -= board[cur][i]; } return dfs(m, n, cur+1); } int main(){ int n = 0,m = 0; while (scanf(" %d %d",&m,&n) != EOF) { memset(board, 0, sizeof(board)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf(" %d",&board[i][j]); } } memset(now, 0, sizeof(now)); if (dfs(m, n, 1)) { printf("Yes, I found itn"); }else{ printf("It is impossiblen"); } } return 0; } |
搜索题，但是BFS不可以，DFS的话优化还特别寸，写了几个版本都过不了，挺邪乎的。
PS：好长时间没做题，想必是遭了报应了。
