Untitled
unknown
plain_text
a year ago
11 kB
4
Indexable
Never
#include <iostream> using namespace std; #define MAXR 99 #define MAXC 26 struct Cell{ int rFirst, cFirst; int rSecond, cSecond; int type; Cell(){ rFirst = cFirst = rSecond = cSecond = type = -1; } Cell(int rFirst, int cFirst,int rSecond, int cSecond, int type){ this->rFirst = rFirst; this->cFirst = cFirst; this->rSecond = rSecond; this->cSecond = cSecond; this->type = type; } void reset(){ rFirst = cFirst = rSecond = cSecond = type = -1; } void set(int rFirst, int cFirst,int rSecond, int cSecond, int type){ this->rFirst = rFirst; this->cFirst = cFirst; this->rSecond = rSecond; this->cSecond = cSecond; this->type = type; } }BoardCell[MAXR+1][MAXC+1]; long long board[MAXR+1][MAXC+1]; bool visited[MAXR+1][MAXR+1]; int r, c; void init(int C, int R) { r = R; c = C; for(int i = 1; i <= R; ++i){ for(int j = 1; j <= C; ++j){ board[i][j] = 0; BoardCell[i][j].reset(); } } } bool convertToInt(long long& res, char input[]){ if(input[0] >= 'A' && input[0] <= 'Z'){ return false; } if(input[0] == '-'){ for(int i = 1; input[i] != '\0'; ++i){ res = res*10 + input[i] - '0'; } res = res * -1; } else{ for(int i = 0; input[i] != '\0'; ++i){ res = res*10 + input[i] - '0'; } } return true; } void set(int col, int row, char input[]) { long long val = 0; bool ok = convertToInt(val, input); if(ok){ board[row][col] = val; BoardCell[row][col].type = 0; return; } int rFirst = input[4] - 'A', cFirst = input[5] - '0'; int rSecond = input[7] - 'A', cSecond = input[8] - '0'; switch (input[0]) { case 'A': BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 1); return; case 'M': if(input[2] == 'U'){ //MUL BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 2); return; } else if(input[2] =='A'){ //MAX BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 3); return; } else{ //MIN BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 4); return; } case 'S': if(input[3] == 'M'){ BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 5); } else{ BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 6); //sub return; } case 'D': BoardCell[row][col] = Cell(rFirst, cFirst, rSecond, cSecond, 7); return; } } int cal(int x, int y){ if(BoardCell[x][y].type == 0 || BoardCell[x][y].type == -1){ return board[x][y]; } if(visited[x][y] == true){ return 0; } visited[x][y] = true; switch (BoardCell[x][y].type) { case 1: board[x][y] = cal(BoardCell[x][y].rFirst, BoardCell[x][y].cFirst) + cal(BoardCell[x][y].rSecond, BoardCell[x][y].cSecond); break; case 2: board[x][y] = cal(BoardCell[x][y].rFirst, BoardCell[x][y].cFirst) * cal(BoardCell[x][y].rSecond, BoardCell[x][y].cSecond); break; case 3: { long long s = -1000000000; if(BoardCell[x][y].rFirst == BoardCell[x][y].rSecond){ for(int i = BoardCell[x][y].cFirst; i <= BoardCell[x][y].cSecond; ++i){ int v = cal(BoardCell[BoardCell[x][y].rFirst][i].rFirst, BoardCell[BoardCell[x][y].rFirst][i].rSecond); if(s < v){ s = v; } } } else{ for(int i = BoardCell[x][y].rFirst; i <= BoardCell[x][y].rSecond; ++i){ int v = cal(BoardCell[i][BoardCell[x][y].cFirst].rFirst, BoardCell[i][BoardCell[x][y].cFirst].rSecond); if(s < v){ s = v; } } } board[x][y] = s; break;} case 4: { long long s = 1000000000; if(BoardCell[x][y].rFirst == BoardCell[x][y].rSecond){ for(int i = BoardCell[x][y].cFirst; i <= BoardCell[x][y].cSecond; ++i){ long long v = cal(BoardCell[BoardCell[x][y].rFirst][i].rFirst, BoardCell[BoardCell[x][y].rFirst][i].rSecond); if(s > v){ s = v; } } } else{ for(int i = BoardCell[x][y].rFirst; i <= BoardCell[x][y].rSecond; ++i){ long long v = cal(BoardCell[i][BoardCell[x][y].cFirst].rFirst, BoardCell[i][BoardCell[x][y].cFirst].rSecond); if(s > v){ s = v; } } } board[x][y] = s; break; } case 5: { long long s = 0; if(BoardCell[x][y].rFirst == BoardCell[x][y].rSecond){ for(int i = BoardCell[x][y].cFirst; i <= BoardCell[x][y].cSecond; ++i){ s += cal(BoardCell[BoardCell[x][y].rFirst][i].rFirst, BoardCell[BoardCell[x][y].rFirst][i].rSecond); } } else{ for(int i = BoardCell[x][y].rFirst; i <= BoardCell[x][y].rSecond; ++i){ s += cal(BoardCell[i][BoardCell[x][y].cFirst].rFirst, BoardCell[i][BoardCell[x][y].cFirst].rSecond); } } board[x][y] = s; break; } case 6: board[x][y] = cal(BoardCell[x][y].rFirst, BoardCell[x][y].cFirst) - cal(BoardCell[x][y].rSecond, BoardCell[x][y].cSecond); break; case 7: board[x][y] = cal(BoardCell[x][y].rFirst, BoardCell[x][y].cFirst) / cal(BoardCell[x][y].rSecond, BoardCell[x][y].cSecond); break; } return board[x][y]; } void update(int value[MAXR][MAXC]) { for(int i = 0; i < r; ++i){ for(int j = 0; j < c; ++j){ visited[i+1][j+1] = false; } } for(int i = 0; i < r; ++i){ for(int j = 0; j < c; ++j){ int v = cal(i+1,j+1); value[i][j] = v; } } } int main(){ init(5, 5); set(3, 2, "5"); set(5, 2, "13"); set(1, 5, "2"); set(2, 1, "6"); set(1, 1, "-9"); set(3, 4, "9"); set(2, 2, "3"); set(2, 4, "7"); set(5, 3, "2"); set(3, 1, "5"); set(3, 4, "-9"); set(1, 2, "SUM(A5,E5"); set(4, 2, "8"); set(4, 5, "MUL(E2,E5)"); set(2, 2, "SUB(E4,B4)"); set(1, 4, "-9"); set(1, 5, "ADD(C2,A4)"); int vv[MAXR][MAXC]; update(vv); return 0; } /* int rfirst = input[4] - 'A', cFirst = input[5] - '0'; int rSecond = input[7] - 'A', cSecond = input[8] - '0'; switch (input[0]) { case 'A': board[row][col] = board[rfirst][cFirst] + board[rSecond][cSecond]; return; case 'M': if(input[2] == 'U'){ //MUL board[row][col] = board[rfirst][cFirst] * board[rSecond][cSecond]; return; } else if(input[2] =='A'){ //MAX long long s = -10000000001; if(rfirst == rSecond){ for(int i = cFirst; i <= cSecond; ++i){ if(s < board[rfirst][i]){ s = board[rfirst][i]; } } board[row][col] = s; return; } if(cFirst == cSecond){ for(int i = rfirst; i <= rSecond; ++i){ if(s < board[i][cFirst]){ s = board[i][cFirst]; } } board[row][col] = s; return; } return; } else{ //MIN long long s = 10000000001; if(rfirst == rSecond){ for(int i = cFirst; i <= cSecond; ++i){ if(s > board[rfirst][i]){ s = board[rfirst][i]; } } board[row][col] = s; return; } if(cFirst == cSecond){ for(int i = rfirst; i <= rSecond; ++i){ if(s > board[i][cFirst]){ s = board[i][cFirst]; } } board[row][col] = s; return; } return; } case 'S': if(input[3] == 'M'){ //sum long long s = 0; if(rfirst == rSecond){ for(int i = cFirst; i <= cSecond; ++i){ s += board[rfirst][i]; } board[row][col] = s; return; } if(cFirst == cSecond){ for(int i = rfirst; i <= rSecond; ++i){ s += board[i][cFirst]; } board[row][col] = s; return; } } else{ //sub board[row][col] = board[rfirst][cFirst] - board[rSecond][cSecond]; return; } case 'D': board[row][col] = board[rfirst][cFirst] / board[rSecond][cSecond]; return; } */ #define MAXR 99 #define MAXC 26 struct Node { int x1, y1, x2, y2, type; Node() {} Node(int x1, int y1, int x2, int y2, int type) : x1(x1), y1(y1), x2(x2), y2(y2), type(type) {} }; Node v[MAXR][MAXC]; int A[MAXR][MAXC]; bool calc[MAXR][MAXC]; int N, M; char T_[] = { 'D', 'B', 'L', 'V', 'X', 'N', 'M' }; int T[256]; void init(int C, int R) { N = R; M = C; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { A[i][j] = 0; v[i][j] = Node(0, 0, 0, 0, -1); } } for (int i = 0; i < 7; i++) { T[T_[i]] = i; } } int _atoi(char const *c) { int value = 0; int positive = 1; if (*c == '\0') { return 0; } if (*c == '-') { positive = -1; } while (*c) { if (*c >= '0' && *c <= '9') { value = value * 10 + *c - '0'; } c++; } return value * positive; } void set(int col, int row, char input[]) { col--; row--; if (input[0] == '-' || ('0' <= input[0] && input[0] <= '9')) { A[row][col] = _atoi(input); v[row][col] = Node(0, 0, 0, 0, 7); return; } int type = T[input[2]]; int i = 4; int y1 = input[i++] - 'A'; int x1 = 0; while ('0' <= input[i] && input[i] <= '9') { x1 = x1 * 10 + input[i++] - '0'; } i++; int y2 = input[i++] - 'A'; int x2 = 0; while ('0' <= input[i] && input[i] <= '9') { x2 = x2 * 10 + input[i++] - '0'; } v[row][col] = Node(x1 - 1, y1, x2 - 1, y2, type); } int _max(int a, int b) { if (a > b) { return a; } return b; } int _min(int a, int b) { if (a < b) { return a; } return b; } int update(int x, int y) { if (calc[x][y] || v[x][y].type == 7) { return A[x][y]; } calc[x][y] = true; if (v[x][y].type == -1) { A[x][y] = 0; return 0; } int type = v[x][y].type; int x1 = v[x][y].x1; int y1 = v[x][y].y1; int x2 = v[x][y].x2; int y2 = v[x][y].y2; if (type == 0) { A[x][y] = update(x1, y1) + update(x2, y2); } else if (type == 1) { A[x][y] = update(x1, y1) - update(x2, y2); } else if (type == 2) { A[x][y] = update(x1, y1) * update(x2, y2); } else if (type == 3) { A[x][y] = update(x1, y1) / update(x2, y2); } else { int res = update(x1, y1); for (int i = x1; i <= x2; i++) { for (int j = y1; j <= y2; j++) { if (i == x1 && j == y1) continue; if (type == 4) { res = _max(res, update(i, j)); } else if (type == 5) { res = _min(res, update(i, j)); } else { res += update(i, j); } } } A[x][y] = res; } return A[x][y]; } void update(int value[MAXR][MAXC]) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { calc[i][j] = false; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { value[i][j] = update(i, j); } } }