#include #include using namespace std; int n, m, tot_min=9999; int red_x, red_y, blue_x, blue_y; char map[11][11]; bool visited[11][11]={0,}; string a; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; int beam(int i, int r, int b, bool red, bool cancel){ int x, y, tmp_x, tmp_y; int red_y=r/m, red_x=r%m, blue_y=b/m, blue_x=b%m; if(red){ x=red_x; y=red_y; tmp_x=blue_x; tmp_y=blue_y; } else{ x=blue_x; y=blue_y; tmp_x=red_x; tmp_y=red_y; } while(map[y+dy[i]][x+dx[i]]!='#' && !(y+dy[i]==tmp_y && x+dx[i]==tmp_x)){ y+=dy[i]; x+=dx[i]; if(red){ if(!cancel) visited[y][x]=1; else visited[y][x]=0; } if(!red && map[y][x]=='O') return -1; } return y*m+x; } int promising(int r, int b, int i){ bool blue=0; red_y=r/m, red_x=r%m, blue_y=b/m, blue_x=b%m; int ny=red_y+dy[i], nx=red_x+dx[i]; //one step if(visited[ny][nx]==1) return -1; if(map[ny][nx]=='#') return 0; if(ny==blue_y && nx==blue_x){ if(map[ny+dy[i]][nx+dx[i]]=='#') return 0; else blue=1; } if(map[ny][nx]=='O') return 3; while(1){ ny+=dy[i], nx+=dx[i]; if(visited[ny][nx]==1) return -1; if(map[ny][nx]=='B') blue=1; if(map[ny][nx]=='#') break; if(map[ny][nx]=='O'){ if(blue) return -1; else return 3; } } if(blue) return 2; //blue first else return 1; } void backtrack(int r, int b, int rank){ if(rank>10) return; //cout << r << " " << b << endl; for(int i=0; i<4; i++){ int res=promising(r,b,i); //cout << res << endl; if(res==0){ int blue=beam(i,r,b,0,0); if(blue==-1) continue; if(blue==b) continue; backtrack(r, blue, rank+1); } if(res==1){ //red first int red=beam(i,r,b,1,0); int blue=beam(i,red,b,0,0); if(blue==-1){ beam(i,r,b,1,1); continue; } //cout << i << endl; backtrack(red, blue, rank+1); beam(i,r,b,1,1); } else if(res==2){ //blue first int blue=beam(i,r,b,0,0); int red=beam(i,r,blue,1,0); //cout << i << endl; backtrack(red, blue, rank+1); beam(i,r,b,1,1); } else if(res==3){ int blue=beam(i,r,b,0,0); if(blue/m+dy[i]==r/m && blue%m+dx[i]==r%m) continue; if(rank> n >> m; for(int i=0; i> a; for(int j=0; j10) cout << -1; else cout << tot_min; return 0; }

제출 #106064

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: