Untitled
unknown
plain_text
5 months ago
1.9 kB
1
Indexable
Never
#include <iostream> using namespace std; int N, M; char a[300][300]; int visited[300][300]; int dx[] = {-1, 0, 0, 1}; int dy[] = { 0, 1, -1, 0}; int XStart, YStart, XEnd, YEnd; int ans; int attack(int x, int y, int dx, int dy, bool at){ int x1 = x; int y1 = y; int cnt = 0; while(x1 >= 0 && y1 >= 0 && x1 < N && y1 < M){ if(at){ if(a[x1][y1] == 'B') { a[x1][y1] = 'Z'; cnt++; } }else { if(a[x1][y1] == 'Z'){ a[x1][y1] = 'B'; cnt++; } } x1 = x1 + dx; y1 = y1 + dy; } return cnt; } void Try(int x, int y, int step){ if(x == XEnd && y == YEnd){ if(step < ans) ans = step; return; } visited[x][y] = 1; for(int i = 0; i < 4; i++){ int x1 = x + dx[i]; int y1 = y + dy[i]; if(x1 >= 0 && y1 >= 0 && x1 < N && y1 < M && visited[x1][y1] == 0){ visited[x1][y1] = 1; if(a[x1][y1] == 'R' || a[x1][y1] == 'S') break; if(a[x1][y1] == 'B'){ step = step + attack(x1, y1, dx[i], dy[i], 1); Try(x1, y1, step); step = step - attack(x1, y1, dx[i], dy[i], 0); }else { step++; Try(x1, y1, step); step--; } visited[x1][y1] = 0; } } } void reset(){ for(int i = 0; i < 300; i++){ for(int j = 0; j < 300; j++){ a[i][j] = ' '; visited[i][j] = 0; } } } int main(){ // freopen("input.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M; reset(); for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> a[i][j]; if(a[i][j] == 'Y'){ XStart = i; YStart = j; } if(a[i][j] == 'T'){ XEnd = i; YEnd = j; } } } ans = 1000000; Try(XStart, YStart, 0); cout << "Case #" << tc << endl; if(ans == 1000000){ cout << -1 << endl; }else{ cout << ans << endl; } } return 0; }