Skip to content

Commit 2dbe407

Browse files
daiwbdaiwb
committed
LeetCode 05/30/2014
1 parent fac3887 commit 2dbe407

2 files changed

Lines changed: 163 additions & 0 deletions

File tree

‎LeetCode/exist.cpp‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
31+
int row, col, len;
32+
vector<VI> vv;
33+
bool valid;
34+
vector<vector<char> > board;
35+
string word;
36+
37+
class Solution {
38+
public:
39+
void dfs(int x, int y, int idx) {
40+
if (valid) return;
41+
if (idx == len) {
42+
valid = true;
43+
return;
44+
}
45+
REP(i,4) {
46+
int tx = x + dir[i][0], ty = y + dir[i][1];
47+
if (tx < 0 || tx >= row || ty < 0 || ty >= col) continue;
48+
if (board[tx][ty] != word[idx]) continue;
49+
if (vv[tx][ty] == 1) continue;
50+
vv[tx][ty] = 1;
51+
dfs(tx, ty, idx + 1);
52+
vv[tx][ty] = 0;
53+
}
54+
}
55+
bool isok(int x, int y) {
56+
vv.assign(row, VI(col, 0));
57+
valid = false;
58+
vv[x][y] = 1;
59+
dfs(x, y, 1);
60+
return valid;
61+
}
62+
bool exist(vector<vector<char> >& _board, string _word) {
63+
board = _board;
64+
word = _word;
65+
row = board.size();
66+
if (row == 0) return false;
67+
col = board[0].size();
68+
if (col == 0) return false;
69+
len = word.length();
70+
if (len == 0) return false;
71+
REP(i,row) {
72+
REP(j,col) {
73+
if (board[i][j] != word[0]) continue;
74+
if (isok(i, j)) return true;
75+
}
76+
}
77+
return false;
78+
}
79+
};
80+
81+
int main() {
82+
Solution s = Solution();
83+
vector<vector<char> > board;
84+
string t[] = {"ABCE", "SFCS", "ADEE"};
85+
REP(i,3) {
86+
vector<char> q;
87+
REP(j,4) {
88+
q.PB(t[i][j]);
89+
}
90+
board.PB(q);
91+
}
92+
//cout << s.exist(board, "ABCCED") << endl;
93+
//cout << s.exist(board, "SEE") << endl;
94+
cout << s.exist(board, "ABCB") << endl;
95+
return 0;
96+
}

‎LeetCode/subsets.cpp‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
#include <algorithm>
2+
#include <iostream>
3+
#include <sstream>
4+
#include <string>
5+
#include <vector>
6+
#include <queue>
7+
#include <set>
8+
#include <map>
9+
#include <cstdio>
10+
#include <cstdlib>
11+
#include <cctype>
12+
#include <cmath>
13+
#include <string>
14+
#include <cstring>
15+
using namespace std;
16+
17+
#define REP(i,n) for(int i=0;i<(n);++i)
18+
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
19+
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
20+
#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
21+
#define CLR(x) memset((x),0,sizeof((x)))
22+
#define MP make_pair
23+
#define MPI make_pair<int, int>
24+
#define PB push_back
25+
typedef long long LL;
26+
typedef vector<int> VI;
27+
typedef vector<string> VS;
28+
typedef pair<int, int> PI;
29+
30+
class Solution {
31+
public:
32+
VI mm;
33+
vector<VI> res;
34+
int n;
35+
void doit(int st, VI& S) {
36+
mm.PB(-1);
37+
FOR(i,st,n-1) {
38+
mm.back() = S[i];
39+
res.PB(mm);
40+
doit(i + 1, S);
41+
}
42+
mm.pop_back();
43+
}
44+
vector<vector<int> > subsets(vector<int> &S) {
45+
n = S.size();
46+
res.clear();
47+
mm.clear();
48+
res.PB(mm);
49+
sort(S.begin(), S.end());
50+
doit(0, S);
51+
return res;
52+
}
53+
};
54+
55+
int main() {
56+
Solution s = Solution();
57+
VI S;
58+
S.PB(1);
59+
S.PB(2);
60+
S.PB(3);
61+
vector<VI> res = s.subsets(S);
62+
REP(i,res.size()) {
63+
REP(j,res[i].size()) cout << res[i][j] << " ";
64+
cout << endl;
65+
}
66+
return 0;
67+
}

0 commit comments

Comments
 (0)