BZOJ1102(搜索)

随便写一下的搜索,别的OJ深搜就过了,强大的BZOJ成功栈溢出RE了我并使我屈服地用广搜过掉,第一行手动开栈惨遭无视。

广搜:

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <climits>
  9 #include <iostream>
 10 #include <iomanip>
 11 #include <algorithm>
 12 #include <string>
 13 #include <sstream>
 14 #include <stack>
 15 #include <queue>
 16 #include <set>
 17 #include <map>
 18 #include <vector>
 19 #include <list>
 20 #include <fstream>
 21 #include <bitset>
 22 #define init(a, b) memset(a, b, sizeof(a))
 23 #define rep(i, a, b) for (int i = a; i <= b; i++)
 24 #define irep(i, a, b) for (int i = a; i >= b; i--)
 25 using namespace std;
 26 
 27 typedef double db;
 28 typedef long long ll;
 29 typedef unsigned long long ull;
 30 typedef pair<int, int> P;
 31 const int inf = 0x3f3f3f3f;
 32 const ll INF = 1e18;
 33 
 34 template <typename T> void read(T &x) {
 35     x = 0;
 36     int s = 1, c = getchar();
 37     for (; !isdigit(c); c = getchar())
 38         if (c == '-')    s = -1;
 39     for (; isdigit(c); c = getchar())
 40         x = x * 10 + c - 48;
 41     x *= s;
 42 }
 43 
 44 template <typename T> void write(T x) {
 45     if (x < 0)    x = -x, putchar('-');
 46     if (x > 9)    write(x / 10);
 47     putchar(x % 10 + '0');
 48 }
 49 
 50 template <typename T> void writeln(T x) {
 51     write(x);
 52     puts("");
 53 }
 54 
 55 const int maxn = 1e3 + 5;
 56 int n, A[maxn][maxn], up, down;
 57 bool vis[maxn][maxn];
 58 
 59 int bfs(int x, int y) {
 60     queue<P> Q;
 61     Q.push(P(x, y));
 62     vis[x][y] = true;
 63     bool small = true, equal = true, large = true;
 64     while (!Q.empty()) {
 65         int i = Q.front().first, j = Q.front().second;
 66         Q.pop();
 67         rep(a, -1, 1)    rep(b, -1, 1) {
 68             int nx = i + a, ny = j + b;
 69             if (nx < 1 || nx > n || ny < 1 || ny > n)    continue;
 70 
 71             int val = A[nx][ny], k = -1;
 72             if (val == A[i][j]) {
 73                 if (vis[nx][ny])    continue;
 74                 Q.push(P(nx, ny));
 75                 vis[nx][ny] = true;
 76             } else if (val > A[i][j]) {
 77                 k = 2;
 78             } else    k = 1;
 79 
 80             if (k == 2)    small = false, equal = false;
 81             else if (k == 1)    large = false, equal = false;
 82         }
 83     }
 84     if (equal)    return 0;
 85     if (small)    return 1;
 86     if (large)    return 2;
 87     return -1;
 88 }
 89 
 90 int main() {
 91     read(n);
 92     rep(i, 1, n)    rep(j, 1, n)    read(A[i][j]);
 93     rep(i, 1, n)    rep(j, 1, n) {
 94         if (!vis[i][j]) {
 95             int k = bfs(i, j);
 96             if (k == 0) {
 97                 up++, down++;
 98             } else if (k == 1) {
 99                 up++;
100             } else if (k == 2) {
101                 down++;
102             }
103         }
104     }
105     printf("%d %d\n", up, down);
106     return 0;
107 }

 

深搜:

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <climits>
  9 #include <iostream>
 10 #include <iomanip>
 11 #include <algorithm>
 12 #include <string>
 13 #include <sstream>
 14 #include <stack>
 15 #include <queue>
 16 #include <set>
 17 #include <map>
 18 #include <vector>
 19 #include <list>
 20 #include <fstream>
 21 #include <bitset>
 22 #define init(a, b) memset(a, b, sizeof(a))
 23 #define rep(i, a, b) for (int i = a; i <= b; i++)
 24 #define irep(i, a, b) for (int i = a; i >= b; i--)
 25 using namespace std;
 26 
 27 typedef double db;
 28 typedef long long ll;
 29 typedef unsigned long long ull;
 30 typedef pair<int, int> P;
 31 const int inf = 0x3f3f3f3f;
 32 const ll INF = 1e18;
 33 
 34 template <typename T> void read(T &x) {
 35     x = 0;
 36     int s = 1, c = getchar();
 37     for (; !isdigit(c); c = getchar())
 38         if (c == '-')    s = -1;
 39     for (; isdigit(c); c = getchar())
 40         x = x * 10 + c - 48;
 41     x *= s;
 42 }
 43 
 44 template <typename T> void write(T x) {
 45     if (x < 0)    x = -x, putchar('-');
 46     if (x > 9)    write(x / 10);
 47     putchar(x % 10 + '0');
 48 }
 49 
 50 template <typename T> void writeln(T x) {
 51     write(x);
 52     puts("");
 53 }
 54 
 55 const int maxn = 1e3 + 5;
 56 int n, A[maxn][maxn], up, down;
 57 bool vis[maxn][maxn];
 58 
 59 int dfs(int i, int j) {
 60     vis[i][j] = true;
 61     bool small = true, equal = true, large = true;
 62     rep(a, -1, 1)    rep(b, -1, 1) {
 63         int nx = i + a, ny = j + b;
 64         if (nx < 1 || nx > n || ny < 1 || ny > n)    continue;
 65 
 66         int val = A[nx][ny], k = -1;
 67         if (val == A[i][j]) {
 68             if (vis[nx][ny])    continue;
 69             k = dfs(nx, ny);
 70         } else if (val > A[i][j]) {
 71             k = 2;
 72         } else    k = 1;
 73 
 74         if (k == 2)    small = false, equal = false;
 75         else if (k == 1)    large = false, equal = false;
 76         else if (k == 0)    small = false, large = false;
 77         else    small = false, equal = false, large = false;
 78     }
 79     if (equal)    return 0;
 80     if (small)    return 1;
 81     if (large)    return 2;
 82     return -1;
 83 }
 84 
 85 int main() {
 86     read(n);
 87     rep(i, 1, n)    rep(j, 1, n)    read(A[i][j]);
 88     rep(i, 1, n)    rep(j, 1, n) {
 89         if (!vis[i][j]) {
 90             int k = dfs(i, j);
 91             if (k == 0) {
 92                 up++, down++;
 93             } else if (k == 1) {
 94                 up++;
 95             } else if (k == 2) {
 96                 down++;
 97             }
 98         }
 99     }
100     printf("%d %d\n", up, down);
101     return 0;
102 }

 

上一篇:CH2906 武士风度的牛(算竞进阶习题)


下一篇:孤岛营救问题 (BFS+状压)