Experiment #N: North: Rn, South: Rs, East: Re, West: Rw
| input | output |
|---|---|
10 5 ..####.... ..o..o.... ..####.#o. ......##.. .o#####... 1 4 |
Experiment #1: North: 0, South: 1, East: 0, West: 0 |
1 /** 2 Create By yzx - stupidboy 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cmath> 8 #include <deque> 9 #include <vector> 10 #include <queue> 11 #include <iostream> 12 #include <algorithm> 13 #include <map> 14 #include <set> 15 #include <ctime> 16 #include <iomanip> 17 using namespace std; 18 typedef long long LL; 19 typedef double DB; 20 #define For(i, s, t) for(int i = (s); i <= (t); i++) 21 #define Ford(i, s, t) for(int i = (s); i >= (t); i--) 22 #define Rep(i, t) for(int i = (0); i < (t); i++) 23 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--) 24 #define rep(i, x, t) for(int i = (x); i < (t); i++) 25 #define MIT (2147483647) 26 #define INF (1000000001) 27 #define MLL (1000000000000000001LL) 28 #define sz(x) ((int) (x).size()) 29 #define clr(x, y) memset(x, y, sizeof(x)) 30 #define puf push_front 31 #define pub push_back 32 #define pof pop_front 33 #define pob pop_back 34 #define ft first 35 #define sd second 36 #define mk make_pair 37 inline void SetIO(string Name) 38 { 39 string Input = Name+".in", 40 Output = Name+".out"; 41 freopen(Input.c_str(), "r", stdin), 42 freopen(Output.c_str(), "w", stdout); 43 } 44 45 46 inline int Getint() 47 { 48 int Ret = 0; 49 char Ch = ‘ ‘; 50 bool Flag = 0; 51 while(!(Ch >= ‘0‘ && Ch <= ‘9‘)) 52 { 53 if(Ch == ‘-‘) Flag ^= 1; 54 Ch = getchar(); 55 } 56 while(Ch >= ‘0‘ && Ch <= ‘9‘) 57 { 58 Ret = Ret * 10 + Ch - ‘0‘; 59 Ch = getchar(); 60 } 61 return Flag ? -Ret : Ret; 62 } 63 64 const int N = 510; 65 const int Dx[] = {1, -1, 0, 0}, Dy[] = {0, 0, -1, 1}; 66 const int Where[] = {1, 0, 3, 2}; 67 int m, n; 68 char Map[N][N]; 69 typedef pair<int, int> II; 70 II Point[N * N], Que[N * N * 4]; 71 int Tot; 72 int Dp[N][N], Mark[N][N], Come[N][N]; 73 74 inline void Input() 75 { 76 scanf("%d%d", &m, &n); 77 For(i, 1, n) 78 { 79 getchar(); 80 scanf("%s", Map[i] + 1); 81 } 82 } 83 84 inline bool Check(int x, int y) 85 { 86 if(x < 1 || x > n || y < 1 || y > m) return 0; 87 if(Map[x][y] == ‘.‘) return 0; 88 return 1; 89 } 90 91 inline void Bfs(int Stx, int Sty) 92 { 93 For(i, 1, n) 94 For(j, 1, m) 95 Dp[i][j] = INF, Mark[i][j] = Come[i][j] = -1; 96 int Tx, Ty, Head = 1, Tail = 0; 97 Rep(i, 4) 98 { 99 Tx = Stx + Dx[i]; 100 Ty = Sty + Dy[i]; 101 if(Check(Tx, Ty)) 102 { 103 Dp[Tx][Ty] = 1; 104 Mark[Tx][Ty] = i; 105 Come[Tx][Ty] = Where[i]; 106 Que[++Tail] = mk(Tx, Ty); 107 } 108 } 109 110 while(Head <= Tail) 111 { 112 II Now = Que[Head++]; 113 int x = Now.ft, y = Now.sd; 114 Rep(i, 4) 115 { 116 Tx = x + Dx[i]; 117 Ty = y + Dy[i]; 118 if(Check(Tx, Ty)) 119 { 120 if(Dp[Tx][Ty] > Dp[x][y] + 1 || 121 (Dp[Tx][Ty] == Dp[x][y] + 1 && Come[Tx][Ty] > Where[i])) 122 { 123 Dp[Tx][Ty] = Dp[x][y] + 1; 124 Mark[Tx][Ty] = Mark[x][y]; 125 Come[Tx][Ty] = Where[i]; 126 Que[++Tail] = mk(Tx, Ty); 127 } 128 } 129 } 130 } 131 } 132 133 inline void Solve() 134 { 135 Ford(i, n, 1) 136 For(j, 1, m) 137 if(Map[i][j] == ‘o‘) 138 Point[++Tot] = mk(i, j); 139 140 int Opt, Ans[4]; 141 scanf("%d", &Opt); 142 For(Test, 1, Opt) 143 { 144 int x; 145 scanf("%d", &x); 146 Bfs(Point[x].ft, Point[x].sd); 147 148 Rep(i, 4) Ans[i] = 0; 149 For(i, 1, Tot) 150 if(x != i && Mark[Point[i].ft][Point[i].sd] != -1) 151 Ans[Mark[Point[i].ft][Point[i].sd]]++; 152 printf("Experiment #%d: North: %d, South: %d, East: %d, West: %d\n", 153 Test, Ans[1], Ans[0], Ans[3], Ans[2]); 154 } 155 } 156 157 int main() 158 { 159 #ifndef ONLINE_JUDGE 160 SetIO("A"); 161 #endif 162 Input(); 163 Solve(); 164 return 0; 165 }
原文：http://www.cnblogs.com/StupidBoy/p/4999086.html
