BZOJ1102（搜索）

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

广搜：

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <ctime>

 #include <cctype>

 #include <climits>

 #include <iostream>

 #include <iomanip>

 #include <algorithm>

 #include <string>

 #include <sstream>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <vector>

 #include <list>

 #include <fstream>

 #include <bitset>

 #define init(a, b) memset(a, b, sizeof(a))

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 #define irep(i, a, b) for (int i = a; i >= b; i--)

 using namespace std;

 typedef double db;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int, int> P;

 const int inf = 0x3f3f3f3f;

 const ll INF = 1e18;

 template <typename T> void read(T &x) {

     x = ;

     int s = , c = getchar();

     for (; !isdigit(c); c = getchar())

         if (c == '-')    s = -;

     for (; isdigit(c); c = getchar())

         x = x *  + c - ;

     x *= s;

 }

 template <typename T> void write(T x) {

     if (x < )    x = -x, putchar('-');

     if (x > )    write(x / );

     putchar(x %  + '');

 }

 template <typename T> void writeln(T x) {

     write(x);

     puts("");

 }

 const int maxn = 1e3 + ;

 int n, A[maxn][maxn], up, down;

 bool vis[maxn][maxn];

 int bfs(int x, int y) {

     queue<P> Q;

     Q.push(P(x, y));

     vis[x][y] = true;

     bool small = true, equal = true, large = true;

     while (!Q.empty()) {

         int i = Q.front().first, j = Q.front().second;

         Q.pop();

         rep(a, -, )    rep(b, -, ) {

             int nx = i + a, ny = j + b;

             if (nx <  || nx > n || ny <  || ny > n)    continue;

             int val = A[nx][ny], k = -;

             if (val == A[i][j]) {

                 if (vis[nx][ny])    continue;

                 Q.push(P(nx, ny));

                 vis[nx][ny] = true;

             } else if (val > A[i][j]) {

                 k = ;

             } else    k = ;

             if (k == )    small = false, equal = false;

             else if (k == )    large = false, equal = false;

         }

     }

     if (equal)    return ;

     if (small)    return ;

     if (large)    return ;

     return -;

 }

 int main() {

     read(n);

     rep(i, , n)    rep(j, , n)    read(A[i][j]);

     rep(i, , n)    rep(j, , n) {

         if (!vis[i][j]) {

             int k = bfs(i, j);

             if (k == ) {

                 up++, down++;

             } else if (k == ) {

                 up++;

             } else if (k == ) {

                 down++;

             }

         }

     }

     printf("%d %d\n", up, down);

     return ;

 }

深搜：

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <ctime>

 #include <cctype>

 #include <climits>

 #include <iostream>

 #include <iomanip>

 #include <algorithm>

 #include <string>

 #include <sstream>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <vector>

 #include <list>

 #include <fstream>

 #include <bitset>

 #define init(a, b) memset(a, b, sizeof(a))

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 #define irep(i, a, b) for (int i = a; i >= b; i--)

 using namespace std;

 typedef double db;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int, int> P;

 const int inf = 0x3f3f3f3f;

 const ll INF = 1e18;

 template <typename T> void read(T &x) {

     x = ;

     int s = , c = getchar();

     for (; !isdigit(c); c = getchar())

         if (c == '-')    s = -;

     for (; isdigit(c); c = getchar())

         x = x *  + c - ;

     x *= s;

 }

 template <typename T> void write(T x) {

     if (x < )    x = -x, putchar('-');

     if (x > )    write(x / );

     putchar(x %  + '');

 }

 template <typename T> void writeln(T x) {

     write(x);

     puts("");

 }

 const int maxn = 1e3 + ;

 int n, A[maxn][maxn], up, down;

 bool vis[maxn][maxn];

 int dfs(int i, int j) {

     vis[i][j] = true;

     bool small = true, equal = true, large = true;

     rep(a, -, )    rep(b, -, ) {

         int nx = i + a, ny = j + b;

         if (nx <  || nx > n || ny <  || ny > n)    continue;

         int val = A[nx][ny], k = -;

         if (val == A[i][j]) {

             if (vis[nx][ny])    continue;

             k = dfs(nx, ny);

         } else if (val > A[i][j]) {

             k = ;

         } else    k = ;

         if (k == )    small = false, equal = false;

         else if (k == )    large = false, equal = false;

         else if (k == )    small = false, large = false;

         else    small = false, equal = false, large = false;

     }

     if (equal)    return ;

     if (small)    return ;

     if (large)    return ;

     return -;

 }

 int main() {

     read(n);

     rep(i, , n)    rep(j, , n)    read(A[i][j]);

     rep(i, , n)    rep(j, , n) {

         if (!vis[i][j]) {

             int k = dfs(i, j);

             if (k == ) {

                 up++, down++;

             } else if (k == ) {

                 up++;

             } else if (k == ) {

                 down++;

             }

         }

     }

     printf("%d %d\n", up, down);

     return ;

 }

巴特西

BZOJ1102（搜索）

最新文章

热门文章