BFS
python 没有数组概念，因此用list
例如dp=[], 表示初始一个空list，然后append来扩充。
dp=[0]*n 表示定义一个长为n的数组，初始值为0
linux 重命名文件是 mv
python range(len): 0..len-1
range(start, end):start, end-1
range(start, end, step): start, start+step…end1(<end)
远程连接25的cmd
mstsc /v:10.20.2.25 /admin
最近一直遇到这个问题
Stack Overflow requires external JavaScript from another domain, which is blocked or failed to load
看到别人GCJ第一题用了DP，我怎么没想到，贪心一直贪了半天，最后挂个蛋回家，小数据都没A。有时候就是一条筋走到底，最优化问题首先想DP
http://stackoverflow.com/questions/30008076/codejam-2015-round-1b-counter-culture
StackOverflow一直审核极其严格的，稍有不规范就删帖，封账号。
但是主要几个都没有解决问题，禁掉USTC的CDN也还是不行。
第一题ON的dp算法还是从一个日本人博客看了，才想到，昨晚完全木有从这里想，觉得第一题就是稍加贪心思想的编程题
http://ijmp320.hatenablog.jp/entry/2015/05/03/135054
查找文件内容
查找目录下的所有文件中是否含有某个字符串
查找目录下的所有文件中是否含有某个字符串
find .|xargs grep -ri “IBM”
查找目录下的所有文件中是否含有某个字符串,并且只打印出文件名
find .|xargs grep -ri “IBM” -l
查找文件名 包含文件名包含3000
find -name ‘3000*.fna’ 找到前缀为3000k 后缀是.fna的文件
CF301Div2ProC
用 DFS 一直T。
改BFS，之前一直都是在取出队列访问，但是这里由于终点要踩两步才算到，因此如果在取出队列访问，那么可能每次放入队列都X，导致一次就认为到了。
这里面适合在扩展的时候 判出口
int main()
{
iOS;
while(cin>>m>>n)
{
for(int i=0;i<m;i++) cin>>str[i];
cin>>x1>>y1>>x2>>y2;
x1--,y1--, x2--, y2--;
if(x1==x2 && y1==y2 && check(x1, y1)) {puts("YES");continue;}
queue<Node> q;
q.push({x1, y1});
bool ok=0;
while(!q.empty())
{
auto cur=q.front();q.pop();
//cout<<cur.x<<" "<<cur.y<<" ";
for(int k=0;k<4;k++)
{
int nx=cur.x+dx[k], ny=cur.y+dy[k];
if(outrange(nx, ny)) continue;
if((nx==x2 && ny==y2) && (str[x2][y2]=='X' || check(x2, y2)))
{
//cout<<"cur: "<<nx<<" "<<ny<<str[x2][y2]<<" "<<check(x2, y2)<<endl;
ok=1;goto L1;
}
//if(cur.x==x2 && cur.y==y2) {ok=1;goto L1;}
if(str[nx][ny]=='X') continue;
str[nx][ny]='X';
q.push({nx, ny});
}
}
L1:puts(ok?"YES":"NO");
}
return 0;
}
今天和shawn king讨论这题，我在想为啥一定要在取出队列判出口呢，一开始标记终点是否是X
就可以区分了。
于是写了一个标准BFS，WA了，后来自己举了一个例子，发现了问题，如果有两条长度一样的路，那么最后两条路刚好把路全部变为X，而如果终点是. 那么算法会认为NO，实际是有YES的
int main()
{
/*
#ifndef ONLINE_JUDGE
freopen ("in.txt" , "r" , stdin);
freopen ("out.txt" , "w" , stdout);
#endif
*/
while(cin>>m>>n)
{
for(int i=0;i<m;i++) cin>>str[i];
cin>>x1>>y1>>x2>>y2;x1--, y1--,x2--,y2--;
queue<Node> q;
bool EndIsX=(str[x2][y2]=='X');
//cout<<"End: "<<EndIsX<<endl;
q.push({x1, y1});
bool ok=0;
while(!q.empty())
{
auto cur=q.front();q.pop();
//cout<<cur.x<<" "<<cur.y<<endl;
if(cur.x==x2 && cur.y==y2 && (EndIsX || Check(x2, y2))) {ok=1;break;}
for(int k=0;k<4;k++)
{
int nx=cur.x+dx[k], ny=cur.y+dy[k];
if(outrange(nx, ny) || (str[nx][ny]=='X' && (nx!=x2 || ny!=y2)) ) continue;
str[nx][ny]='X';
q.push({nx, ny});
}
}
puts(ok?"YES":"NO");
}
return 0;
}
于是乎终于知道这题为啥要在扩展节点的时候判出口了，因为这样两条路可以差1，然后就可以在另一条路把.变为X之前找到需要的路径了
while(cin>>m>>n)
{
for(int i=0;i<m;i++) cin>>str[i];
cin>>x1>>y1>>x2>>y2;x1--, y1--,x2--,y2--;
queue<Node> q;
bool EndIsX=(str[x2][y2]=='X');
//cout<<"End: "<<EndIsX<<endl;
q.push({x1, y1});
bool ok=0;
while(!q.empty())
{
auto cur=q.front();q.pop();
//cout<<cur.x<<" "<<cur.y<<endl;
//for(int i=0;i<m;i++) cout<<str[i]<<endl;
//if(cur.x==x2 && cur.y==y2 && (EndIsX || Check(x2, y2))) {ok=1;break;}
for(int k=0;k<4;k++)
{
int nx=cur.x+dx[k], ny=cur.y+dy[k];
if(outrange(nx, ny))continue;
if(nx==x2 && y2==ny && (str[x2][y2]=='X' || Check(x2, y2))) {ok=1;goto L1;}
if(str[nx][ny]=='X') continue;
str[nx][ny]='X';
q.push({nx, ny});
}
}
L1:puts(ok?"YES":"NO");
}