タイトル

タイトルの説明:
2 D配列では、各行が左から右に増加し、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.
出力:
各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.

に答える

第一反応深さ優先遍歴

#include <cstring>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <stack>
 
using namespace std;
 
 
enum{
    WHITE = 0,
    GRAY,
    BLACK
};
 
struct map_item{
    int val;
    int color;
};
 
 
#define MAX_ROW 1100
#define MAX_COL 1100
 
struct map_item map_table[MAX_ROW][MAX_COL];
 
struct pos{
    int row;
    int col;
};
 
stack<struct pos> pos_store;
 
 
int m, n, key;
 
bool find_key;
 
#define CLR(a)  memset(a, 0, sizeof(a))
 
 
#define CHECK_VAL(pos, kval) ( (map_table[pos.row][pos.col].val == kval ) ? (0) : (map_table[pos.row][pos.col].val > kval ? -1 : 1)) 
 
#define SET_COLOR(pos, kcolor) ( map_table[pos.row][pos.col].color = kcolor )
 
#define CHECK_COLOR(pos, kcolor) ( map_table[pos.row][pos.col].color == kcolor )
 
#define CHECK_RANGE(pos, max_row, max_col) ( !((pos.row < 1) || (pos.row > max_row) || (pos.col < 1) || (pos.col > max_col)))
 
#define GOTO_POS(pos)   do{  \
                                if(CHECK_COLOR(pos, WHITE) && CHECK_RANGE(pos, m, n)){\
                                    SET_COLOR(pos, GRAY);\
                                    pos_store.push(pos);\
                                }\
                        }while(0)
 
#define LEFT_POS(pos)  do{\
                                pos_store.pop();\
                                SET_COLOR(curr_pos, BLACK);\
                        }while(0)
 
#define DBG_POS(pos)    do{\
                            cout << "pos[" << pos.row << "]["<< pos.col << "]" << endl;\
                            cout << "val:" << map_table[pos.row][pos.col].val << endl;\
                            cout << "color:" << map_table[pos.row][pos.col].color << endl;\
                        }while(0)
 
 
 
 
 
int main()
{
    while(cin >> m >> n){
        cin >> key;
        CLR(map_table);  //clean table
        for(int row = 1; row <= m; row++)
            for(int col = 1; col <= n; col++)
                    cin >> map_table[row][col].val;
         
        struct  pos curr_pos, next_pos;
        curr_pos.row = 1;
        curr_pos.col = 1;
        find_key = false;
        GOTO_POS(curr_pos);
 
        while(!pos_store.empty())
        {
            if(find_key){
                break;      /*break! we find ans*/
            }
            curr_pos = pos_store.top();
            LEFT_POS(curr_pos);
 
            //DBG_POS(curr_pos);
            int check_status = CHECK_VAL(curr_pos, key);
            switch(check_status){
                case 0:
                    find_key = true;
                    break;
 
                case 1:
                    next_pos      = curr_pos;
                    next_pos.row += 1;
                    GOTO_POS(next_pos);
 
                    next_pos      =  curr_pos;
                    next_pos.col  += 1;
                    GOTO_POS(next_pos);
                    break;
 
                case -1:
                    next_pos      = curr_pos;
                    next_pos.row -= 1;
                    GOTO_POS(next_pos);
 
                    next_pos      =  curr_pos;
                    next_pos.col  -= 1;
                    GOTO_POS(next_pos);
                    break;  
 
                default:
                    cout << "error" << endl; 
                    exit(-1);
            } 
        }
        cout << (find_key ? "Yes":"No") << endl;
    }
return 0;
}
 
/**************************************************************
    Problem: 1384
    User: xiyanxiyan10
    Language: C++
    Result: Time Limit Exceed
****************************************************************/

よしタイムアウトだ
そこで二分検索を使います

#include <cstring>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <stack>
 
using namespace std;
 
 
#define MAX_ROW 1100
#define MAX_COL 1100
 
int map_table[MAX_ROW][MAX_COL];
 
int tot_row, tot_col, key;
 
int  reverse_flag;
 
bool find_key;
 
#define CLR(a)          memset(a, 0, sizeof(a))
 
/**
 * @brief vist the vertex
 * @param[in] i row num
 * @param[in] j col num
 * @note reverse_flag reverse the table  
 *
 */
#define GET_VAL(i, j) (reverse_flag ? map_table[j][i] : map_table[i][j])
 
#define  REVERSE_TABLE()    do{\
                                tot_row = tot_row^tot_col;\
                                tot_col = tot_row^tot_col;\
                                tot_row = tot_row^tot_col;\
                                reverse_flag ^= 1;\
                            }while(0)
 
#define  INIT_TABLE()     do{\
                                reverse_flag = 0;\
                            }while(0)
 
 
int main()
{
    while(cin >> tot_row >> tot_col){
        cin >> key;
        INIT_TABLE();
        for(int curr_row = 1; curr_row <= tot_row; curr_row++)
            for(int curr_col = 1; curr_col <= tot_col; curr_col++)
                    cin >> map_table[curr_row][curr_col];
 
        find_key = false;
 
        /*binary_search in row, so we make sure col > row*/
        if(tot_col < (tot_row )){
            REVERSE_TABLE();
        }
        for(int curr_row = 1; (curr_row <= tot_row) && ( key > GET_VAL(curr_row, 1) ); curr_row++){
            int left_col = 1;
            int right_col = tot_col;
            int curr_col;
            if(true == find_key){
                    break;
            }
            while(left_col <= right_col){
                   int val;
                   curr_col = ((right_col - left_col) >> 1) + left_col;
                   //cout << " row " << curr_row << " " << curr_col << endl;
                   val  = GET_VAL(curr_row, curr_col);      
                   if(key == val){
                        find_key = true;
                        break;
                   }else if(key > val){
                        left_col =  curr_col + 1;
                   }else{
                        right_col = curr_col - 1;    
                   } 
            }
        }
        cout << (find_key ? "Yes":"No") << endl;
    }
return 0;
}
 
/**************************************************************
    Problem: 1384
    User: xiyanxiyan10
    Language: C++
    Result: Time Limit Exceed
****************************************************************/

依然としてタイムアウトし、最終コードは

#include <cstring>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cstdio>
using namespace std;

#define MAX_ROW 1100
#define MAX_COL 1100

bool find_key;
int tot_row, tot_col, key, tmp;

int main()
{
    int input_key;
    while(~scanf("%d%d%d", &tot_row, &tot_col, &key)){
        find_key = false;
        for(int curr_row = 1; curr_row <= tot_row; curr_row++)
            for(int curr_col = 1; curr_col <= tot_col; curr_col++){
                    scanf("%d", &tmp);
                    if(tmp == key){
                            find_key = true;
                    }
        }
        printf(find_key ? "Yes
":"No
");
    }
return 0;
}

まとめ

コードの実行時データがメモリから来るかレジスタから来るか、IOバッファが効率に致命的になる可能性があるので、注意が必要です.