9度の一回TLを記録する
8207 ワード
タイトル
タイトルの説明:
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バッファが効率に致命的になる可能性があるので、注意が必要です.
第一反応深さ優先遍歴
#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;
}