ural 1287. Mars Canals

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <map>
 11 #include <set>
 12 #include <ctime>
 13 using namespace std;
 14 typedef long long LL;
 15 typedef double DB;
 16 #define For(i, s, t) for(int i = (s); i <= (t); i++)
 17 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)
 18 #define Rep(i, t) for(int i = (0); i < (t); i++)
 19 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
 20 #define rep(i, x, t) for(int i = (x); i < (t); i++)
 21 #define MIT (2147483647)
 22 #define INF (1000000001)
 23 #define MLL (1000000000000000001LL)
 24 #define sz(x) ((int) (x).size())
 25 #define clr(x, y) memset(x, y, sizeof(x))
 26 #define puf push_front
 27 #define pub push_back
 28 #define pof pop_front
 29 #define pob pop_back
 30 #define ft first
 31 #define sd second
 32 #define mk make_pair
 33 inline void SetIO(string Name) {
 34     string Input = Name+".in",
 35     Output = Name+".out";
 36     freopen(Input.c_str(), "r", stdin),
 37     freopen(Output.c_str(), "w", stdout);
 38 }
 39 
 40 inline int Getint() {
 41     int Ret = 0;
 42     char Ch = ‘ ‘;
 43     bool Flag = 0;
 44     while(!(Ch >= ‘0‘ && Ch <= ‘9‘)) {
 45         if(Ch == ‘-‘) Flag ^= 1;
 46         Ch = getchar();
 47     }
 48     while(Ch >= ‘0‘ && Ch <= ‘9‘) {
 49         Ret = Ret*10+Ch-‘0‘;
 50         Ch = getchar();
 51     }
 52     return Flag ? -Ret : Ret;
 53 }
 54 
 55 const int N = 1410;
 56 int n;
 57 char Map[N][N];
 58 
 59 inline void Input() {
 60     scanf("%d", &n);
 61     getchar();
 62     For(i, 1, n) scanf("%s", Map[i]+1);
 63 }
 64 
 65 inline void Updata(int &x, int &y) {
 66     x = max(x, y);
 67     y = 0;
 68 }
 69 
 70 inline bool Check(int x, int y) {
 71     if(x > n || y > n || x < 1 || y < 1) return 0;
 72     return 1;
 73 }
 74 
 75 inline void Next(int &x, int &y) {
 76     x++, y++;
 77 }
 78 
 79 inline int Work(char C) {
 80     int Ret = 0;
 81     int Tmp = 0;
 82     For(i, 1, n) {
 83         For(j, 1, n)
 84             if(Map[i][j] == C) Tmp++;
 85             else Updata(Ret, Tmp);
 86         Updata(Ret, Tmp);
 87     }
 88     
 89     For(j, 1, n) {
 90         For(i, 1, n)
 91             if(Map[i][j] == C) Tmp++;
 92             else Updata(Ret, Tmp);
 93         Updata(Ret, Tmp);
 94     }
 95     
 96     For(i, 1, n) {
 97         for(int x = 1, y = i; Check(x, y); x++, y++)
 98             if(Map[x][y] == C) Tmp++;
 99             else Updata(Ret, Tmp);
100         Updata(Ret, Tmp);
101         
102         for(int x = i, y = 1; Check(x, y); x++, y++)
103             if(Map[x][y] == C) Tmp++;
104             else Updata(Ret, Tmp);
105         Updata(Ret, Tmp);
106         
107         for(int x = n, y = i; Check(x, y); x--, y++)
108             if(Map[x][y] == C) Tmp++;
109             else Updata(Ret, Tmp);
110         Updata(Ret, Tmp);
111         
112         for(int x = i, y = 1; Check(x, y); x--, y++)
113             if(Map[x][y] == C) Tmp++;
114             else Updata(Ret, Tmp);
115         Updata(Ret, Tmp);
116     }
117     
118     return Ret;
119 }
120 
121 inline void Solve() {
122     int Cnt_S = Work(‘S‘);
123     int Cnt_s = Work(‘s‘);
124     if(Cnt_S > Cnt_s) puts("S");
125     else if(Cnt_S < Cnt_s) puts("s");
126     else puts("?");
127     printf("%d\n", max(Cnt_S, Cnt_s));
128 }
129 
130 int main() {
131     #ifndef ONLINE_JUDGE 
132     SetIO("E");
133     #endif 
134     Input();
135     Solve();
136     return 0;
137 }