样例6超时 求帮忙看一下代码
查看原帖
样例6超时 求帮忙看一下代码
278914
zmrlcwds楼主2023/2/28 01:38

我的逻辑是用index 和 mode 同时进行判断,只有字符走向为直线才纳入判断范围 下面是我的代码

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int moved[ 8 ][ 3 ] = { { 1, 0, 1 },  { -1, 0, 2 },  { 0, 1, 3 },
                        { 0, -1, 4 }, { -1, -1, 5 }, { 1, -1, 6 },
                        { -1, 1, 7 }, { 1, 1, 8 } };
int n;
char arr[ 101 ][ 101 ];
int book[ 101 ][ 101 ];
int tb[ 101 ][ 101 ];
string str = "yizhong";
struct node {
  int x, y, mode;
  int index;
};
queue< node > q;

void bfs() {
  while ( !q.empty() ) {
    struct node temp = q.front();
    q.pop();
    int x, y, mode, index;
    for ( int i = 0; i < 8; i++ ) {
      x = temp.x + moved[ i ][ 0 ];
      y = temp.y + moved[ i ][ 1 ];
      mode = moved[ i ][ 2 ];
      if ( !temp.index )
        temp.mode = mode;
      index = temp.index + 1;
      if ( x >= 0 && x < n && y >= 0 && y < n &&
           arr[ x ][ y ] == str[ index ] && temp.mode == mode ) {
        if ( index == 6 ) {
          switch ( mode ) {
          case 2:
            for ( int i = x; i < x + 7; i++ ) {
              tb[ i ][ y ] = 1;
            }
            break;
          case 1:
            for ( int i = x; i >= x - 6; i-- ) {
              tb[ i ][ y ] = 1;
            }
            break;
          case 4:
            for ( int i = y; i < y + 7; i++ ) {
              tb[ x ][ i ] = 1;
            }
            break;
          case 3:
            for ( int i = y; i >= y - 6; i-- ) {
              tb[ x ][ i ] = 1;
            }
            break;
          case 8:
            for ( int i = x; i >= x - 6; i-- ) {
              for ( int j = y; j >= y - 6; j-- )
                if ( j - i == y - x )
                  tb[ i ][ j ] = 1;
            }
            break;
          case 7:
            for ( int i = x; i < x + 7; i++ )
              for ( int j = y; j >= j - 6; j-- )
                if ( j - i == y - x )
                  tb[ i ][ j ] = 1;
            break;
          case 6:
            for ( int i = x; i >= x - 6; i-- )
              for ( int j = y; j < j + 7; j++ )
                if ( j - i == y - x )
                  tb[ i ][ j ] = 1;
            break;
          case 5:
            for ( int i = x; i < x + 7; i++ )
              for ( int j = y; j < j + 7; j++ )
                if ( j - i == y - x )
                  tb[ i ][ j ] = 1;
            break;
          default:
            break;
          }
        } else {
          q.push( { x, y, mode, index } );
        }
      }
    }
  }
}

int main() {
  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      cin >> arr[ i ][ j ];
    }
  }
  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      if ( arr[ i ][ j ] == 'y' ) {
        q.push( { i, j, 0, 0 } );
        bfs();
      }
    }
  }
  for ( int i = 0; i < n; i++ ) {
    for ( int j = 0; j < n; j++ ) {
      if ( tb[ i ][ j ] )
        cout << arr[ i ][ j ];
      else
        cout << "*";
    }
    cout << "\n";
  }
}








2023/2/28 01:38
加载中...