题解：P13224 [GCJ 2015 #2] Pegman
题目大意
通过更改箭头的方向让 Pegman 无论怎样都不会走出网格的边界，输出更改箭头的次数。若无论怎样更改都有可能会走出网格的边界，输出 IMPOSSIBLE。
思路分析
既然我们要让 Pegman 不会走出方格网，那我们就要保证箭头不会指向方格网外（也就是说，要指向其他箭头）。如果指向了方格网外，就对其进行更改，看看另外三个方向会不会指向方格网外。如果另外三个方向能指向其他箭头，我们就进行一次更改。若另外三个方向也只会指向网格外，那就输出 IMPOSSIBLE。
关于箭头的更改，我们并不用在意它到底会指向剩下三个方向的哪一个方向，只需要知道它需要被更改就可以了。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
int R,C;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
for(int i=1;i<=T;i++){
cin>>R>>C;
char a[120][120];
int jsq=0;
for(int j=1;j<=R;j++){
for(int k=1;k<=C;k++){
cin>>a[j][k];
if(a[j][k]!='.'){//jsq用来记录箭头出现的次数
jsq++;
}
}
}
if(jsq==0){//特殊情况：如果没有箭头，直接输出0
cout<<"Case #"<<i<<": "<<jsq<<"\n";
continue;
}
bool ff,f;
int ans=0;
for(int j=1;j<=R;j++){
for(int k=1;k<=C;k++){
if(a[j][k]=='.'){
f=1,ff=0;
continue;
}
f=0;
ff=0;
if(a[j][k]=='>'){//箭头向右的情况
for(int kk=k+1;kk<=C;kk++){
if(a[j][kk]!='.'){//如果它右面有箭头
f=1;//记录一下，不用修改
break;
}
}
if(!f){//如果右面无箭头
for(int kk=1;kk<k;kk++){//向左找
if(a[j][kk]!='.'){
ff=1;//有箭头就做个标记，说明可以做修改，下同
}
}
for(int jj=1;jj<j;jj++){//向上找
if(a[jj][k]!='.'){
ff=1;
}
}
for(int jj=j+1;jj<=R;jj++){//向下找
if(a[jj][k]!='.'){
ff=1;
}
}
}
if(f==0&&ff==0) break;//如果右面无箭头，其他三个方向也没有，说明不可能，直接跳出
}
//后面的下，左，上三种箭头方法同上
if(a[j][k]=='v'){
for(int jj=j+1;jj<=R;jj++){
if(a[jj][k]!='.'){
f=1;
break;
}
}
if(!f){
for(int kk=1;kk<k;kk++){
if(a[j][kk]!='.'){
ff=1;
}
}
for(int jj=1;jj<j;jj++){
if(a[jj][k]!='.'){
ff=1;
}
}
for(int kk=k+1;kk<=C;kk++){
if(a[j][kk]!='.'){
ff=1;
}
}
}
if(f==0&&ff==0) break;
}
if(a[j][k]=='<'){
for(int kk=1;kk<k;kk++){
if(a[j][kk]!='.'){
f=1;
break;
}
}
if(!f){
for(int kk=k+1;kk<=C;kk++){
if(a[j][kk]!='.'){
ff=1;
}
}
for(int jj=1;jj<j;jj++){
if(a[jj][k]!='.'){
ff=1;
}
}
for(int jj=j+1;jj<=R;jj++){
if(a[jj][k]!='.'){
ff=1;
}
}
}
if(f==0&&ff==0) break;
}
if(a[j][k]=='^'){
for(int jj=1;jj<j;jj++){
if(a[jj][k]!='.'){
f=1;
break;
}
}
if(!f){
for(int kk=1;kk<k;kk++){
if(a[j][kk]!='.'){
ff=1;
}
}
for(int kk=1+k;kk<=C;kk++){
if(a[j][kk]!='.'){
ff=1;
}
}
for(int jj=j+1;jj<=R;jj++){
if(a[jj][k]!='.'){
ff=1;
}
}
}
if(f==0&&ff==0) break;
}
if(ff==1) ans++;//如果做出了修改，修改次数加一
}
if((ff==0&&f==0)){ cout<<"Case #"<<i<<": IMPOSSIBLE"<<"\n";break;}//如果四个方向都没有箭头，输出不可能
}
if(f==1||(f==0&&ff==1)) cout<<"Case #"<<i<<": "<<ans<<"\n";//箭头的方向本来就有箭头或修改后的方向有箭头，输出修改次数
}
return 0;
}