专栏文章

题解：P13224 [GCJ 2015 #2] Pegman

CCute_F
P13224题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miox0ri0
此快照首次捕获于
2025/12/03 02:32
3 个月前
此快照最后确认于
2025/12/03 02:32
3 个月前
查看原文

题目大意

通过更改箭头的方向让 Pegman 无论怎样都不会走出网格的边界，输出更改箭头的次数。若无论怎样更改都有可能会走出网格的边界，输出 IMPOSSIBLE。

思路分析

既然我们要让 Pegman 不会走出方格网，那我们就要保证箭头不会指向方格网外（也就是说，要指向其他箭头）。如果指向了方格网外，就对其进行更改，看看另外三个方向会不会指向方格网外。如果另外三个方向能指向其他箭头，我们就进行一次更改。若另外三个方向也只会指向网格外，那就输出 IMPOSSIBLE。
关于箭头的更改，我们并不用在意它到底会指向剩下三个方向的哪一个方向，只需要知道它需要被更改就可以了。

AC code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...