电路维修

输入文件包含多组测试数据。第一行包含一个整数T 表示测试数据的数目。
对于每组测试数据，第一行包含正整数R 和C，表示电路板的行数和列数。
之后R 行，每行C 个字符，字符是"/"和"\"中的一个，表示标准件的方向。

C++11(clang++ 3.9) 解法, 执行用时: 60ms, 内存消耗: 3224K, 提交时间: 2020-08-25 11:30:55

#include<bits/stdc++.h>
using namespace std;
char s[550][550];
int r,c;
struct node{
	int i,j,step;
}Node;
deque<node> dq;
bool vis[550][550];
void judge(int x,int y,int sx,int sy,int sp,char ch){
	if(x>=0&&y>=0&&x<=r&&y<=c&&vis[x][y]==false){
		if(s[sx][sy]==ch)  dq.push_front((node){x,y,sp});
		else  dq.push_back((node){x,y,sp+1});
	}
}
int bfs(){
    while(dq.size())  dq.pop_back();
	Node.i=Node.j=Node.step=0;
	dq.push_front(Node);
	while(dq.size()){
		node now=dq.front();
		dq.pop_front();
		if(vis[now.i][now.j])  continue;
		vis[now.i][now.j]=true;
		if(now.i==r&&now.j==c)  return now.step;
		int x=now.i,y=now.j;
		judge(x+1,y+1,x+1,y+1,now.step,'\\');
		judge(x-1,y-1,x,y,now.step,'\\');
		judge(x+1,y-1,x+1,y,now.step,'/');
		judge(x-1,y+1,x,y+1,now.step,'/');
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		memset(vis,false,sizeof(vis));
		cin>>r>>c;
		for(int i=1;i<=r;i++){
			for(int j=1;j<=c;j++){
				cin>>s[i][j];
			}
		}
		if((r+c)&1)  cout<<"NO SOLUTION"<<endl;
		else  cout<<bfs()<<endl;
	}
	return 0;
}

详情